【我解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;
else if(right > (BUFFERSIZE-2 - value))
{
low = value;
right = 0;
left = 0;
}
else if(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 )。一个不加任何辅助空间，效率高的算法。这个算法来自于一个网友的提醒，这里先谢谢这个网友了。
畅学电子
