2013年08月29日

待字闺中之数组统计


题目描述如下:

给定数组A,大小为n,数组元素为1到n的数字,不过有的数字出现了多次,有的数字没有出现。请给出算法和程序,统计哪些数字没有出现,哪些数字出现了多少次。能够在O(n)的时间复杂度,O(1)的空间复杂度要求下完成么?

分析

题目要求统计数组A中出现的各个元素的次数,限定了数字的大小范围,并且是在O(1)的空间复杂度下完成。在传统的方式下,再另开辟一个数组,统计记录每个数字出现的次数,可以O(n)的时间,但是空间也达到了O(n)。所以需要再寻找另外的办法。

开始,我想到了的方法是这样的,例如对于3,2,2,3,3,2这样的数组,开始遍历,第一个数是3,那么就判断第三个数,如果第三个数也是3,那么第三个数改为2(出现了两次),若第三个数不是3,则交换第一个数和第三个数,然后第三个数改为1(出现了一次),然后依次这样遍历。但是会存在一个问题,到了第三个数,已经无法确定这个数字是统计的3数字出现的次数,还是原数组上出现的初始数值。所以还需要O(n)的空间来标记是哪样数值。这样空间是O(n)。

现在我们只需要有某种方式,标记数组中出现的数字是统计的结果而不是原数组的数字就行了。注意到数组的元素大小是有范围的,在1到n之间,那么我们可以采用一个等价变换,将数字该为负的或者大于n的数字。假如将统计的结果都加上数组可能的最大值N,那么大于N的数一定是统计的结果。这样,到最后只需要遍历一遍数组,将所有大于N的数字都减去N,就得到了统计结果。

代码

基于上面的分析,写出下面的代码:

#include<iostream>
#include<iterator>

using namespace std;

void swap(int &a, int &b){
    if(&a == &b)
        return;
    a = a^b;
    b = a^b;
    a = a^b;
}

void staticData(int *array, int len){
    if(array == NULL || len <= 0)
        return;
    int i = 0;   
    int temp;
    while(i < len){
        if(array[i] == i+1){
            array[i++] = 1 + len;
        }else{
            if(array[i] <= len){
                if(array[i] == array[array[i]-1]){
                    array[array[i]-1] = 2 + len;
                    array[i++] = 0;
                }else if(array[array[i]-1] < len){
                    temp = array[i] - 1;
                    swap(array[i],array[temp]);
                    array[temp] = 1 + len;
                }else{
                    ++array[array[i]-1];
                    array[i++] = 0;
                }
            }else{
                i++;
            }
        }
    }

    for(i = 0; i < len; i++){
        array[i] = array[i] > len? array[i] - len : array[i];
    }
}

int main(){
    //int array[] = {4,3,2,3,1};
    int array[] = {3,2,2,3,3,2};
    int len = sizeof(array) / sizeof(int);

    copy(array,array+len,ostream_iterator<int,char>(cout," "));
    cout << endl;
    
    staticData(array,len);

    copy(array,array+len,ostream_iterator<int,char>(cout," "));
    cout << endl;
}

运行结果如下:

3 2 2 3 3 2 
0 3 3 0 0 0
前一篇: 柱状图中找最大的矩形 后一篇: Openstack Network学习(三)