## 【我解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 )。一個不加任何輔助空間，效率高的算法。這個算法來自于一個網友的提醒，這里先謝謝這個網友了。
