009 特殊的去除数组中重复数字问题

最后更新于:2022-04-01 14:40:23

## 【我解C语言面试题系列】009 特殊的去除数组中重复数字问题 **特殊的去除数组中重复数字问题** 有一个大小为101的数组,里面的数字均介于0到99之间,但是里面的数字仅有一个数字是重复的,请写个函数去除数组中的重复数字。 ~~~ #define       INIT_NUM          -1 #define      BUFFERSIZE    101 ~~~ 方法一:(最最容易想到的办法) ~~~ void RemoveBufferRepNum_00(int buffer[],int *num,int *loc) {    int i,j;       for(i=0;i<100;i++)    {       for(j=i+1;j<101;j++)       {           if(buffer[i] == buffer[j])           {              *num = buffer[j];              *loc = j+1;              return;           }       }    } } ~~~    这个算法最简单,时间复杂度是O(N2) 方法二:(采用hash表法解决) ~~~ void RemoveBufferRepNum_01(int buffer[],int *num,int *loc) {    int tBuffer[BUFFERSIZE];    int i = 0,j = 0;       for(i=0;i<BUFFERSIZE;i++)     //初始化数组       tBuffer[i] = INIT_NUM;    for(i=0;i<BUFFERSIZE;i++)//剔除算法    {       if(tBuffer[buffer[i]] == INIT_NUM)           tBuffer[buffer[i]] = buffer[i];       else           break;    }    *num = buffer[i];    *loc = i+1;       while(i < BUFFERSIZE-1)    {        buffer[i] = buffer[i+1];        i++;    }    buffer[i] = INIT_NUM; } ~~~ 这个办法是用开辅助空间,设置hash表来实现的,总共执行N次就可以了。时间复杂度是:O( N )。但是唯一的弱点就是需要额外的空间。 方法三:(采用折半查找法) ~~~ void RemoveBufferRepNum_02(int buffer[],int *num,int *loc) {    int i,j,low,high,left=0,right=0,value;    low = 0,high = BUFFERSIZE-2;    while(low <= high)//查找重复数字    {       value = (low + high)/2;//low + ((high - low)/2);       for(i = 0;i<BUFFERSIZE;i++)        {           if( buffer[i] > value)              right++;           if( buffer[i] < value)              left++;       }       if( (right == (BUFFERSIZE-2 - value)) && (left == value) )           break;       elseif(right > (BUFFERSIZE-2 - value))       {           low = value;           right = 0;           left = 0;       }       elseif(left > (value-0))       {           high = value;           right = 0;           left = 0;       }    }    j = 0;    for(i = 0;i<BUFFERSIZE;i++)//扫描数组,找到重复数字所在的两个位置    {       if(buffer[i] == value)           j++;       if(j == 2)           break;    }    *num = buffer[i];    *loc = i+1;       while(i < BUFFERSIZE-1)    {        buffer[i] = buffer[i+1];        i++;    }    buffer[i] = INIT_NUM; } ~~~ 这个题目很特殊,数组大小为101,而所有的数字范围是0~99,只有一个是重复的。这里我们就可以采用折半的思想来解决(对于一般的要去掉多个重复数字的情况未必有效)。0~99之间共有100个数字,只有一个重复。 我们可以猜测这个重复的数字是50(处于中间的数字),那么在0~49之间有50个数字,在51~99之间49个数字。如果有一边大于它所应该有的数字个数,那么这个重复数字就肯定在多出来一个那一边。然后再拿出一个中间数字来猜测,不断的去拿中间的数字来猜测,直到猜出那个重复的数字为止。 因为 100 大于 2的6次方,小于 2的7次方。所以我们猜测到这个重复数字的次数最多是7次,最后加上1次查找循环,最多是需要8次扫描数组。时间复杂度是:O( N * log2 N )。相对于方法一来说已经大大的降低了执行次数,相对于方法二来说执行次数是仅仅是log2 N倍,这已经是在不增加额外空间的前提下修改 O(N2) 级别算法的较理想办法了。 方法四: ~~~ void RemoveBufferRepNum_03(int buffer[],int *num,int *loc) {    int i,j,tt;    for(i=0,tt=0;i<BUFFERSIZE;i++)       tt += buffer[i];    tt -= 4950;    for(i=0,j=0;i<BUFFERSIZE;i++)//扫描数组,找到重复数字所在位置    {       if(buffer[i] == tt)           j++;       if(j == 2)           break;    }    *num = buffer[i];    *loc = i+1;    while(i < BUFFERSIZE-1)    {        buffer[i] = buffer[i+1];        i++;    }    buffer[i] = INIT_NUM; } ~~~ 本算法是经过网友的提醒,采用的是求和取余的办法来得到多余数字的,这个算法太巧妙了,很好的利用了题目中所给的条件。 0+1+2+3+4+5+…+98+99 = 4950 。题目说的是多而且只多一个重复的数字,那么所有的数字相加求和后减去 4950,余下的那个数就是重复数字。 然后我们再扫描一遍数组,找到数字的位置即可,时间复杂度是:O( N )。一个不加任何辅助空间,效率高的算法。这个算法来自于一个网友的提醒,这里先谢谢这个网友了。
';