一个整形数组，长为n，元素范围为1~(n-1)，则这个数组内至少有一个数字出现多次，现在要求用O(n)时间,O(1)空间找出一个出现多次的数。
以下为原文：
here's one I got asked which kicked my butt. Write a function that takes in an array of n ints from 1...n-1. For example, an array of 4 numbers which all have values of 1, 2, or 3. There will obviously be at least one duplicate number. Return one of the duplicates (EASY!) - Now do this in order n, without allocating ANY new memory (no hash table or anything).. (Note: I did figure out a solution to this, but the interview didn't seem to like it very much but whatever)..
---------------------------------------------------------------------------------------------------------------------------------------------
answer:
如果允许修改数组，可以利用置换监测，二分也可以做到
如果不允许，可以利用冗余位，变反标记，然后恢复，不过这样本质上的空间不是O（1），虽然ms是O（1）
如n=100,数的范围是1-99,重复的为23
置换监测：
假设把23换成100，则刚好形成一个置换，这样数字刚好构成一些轮换
反过来说刚好是100换成了23造成了一个环的断裂，这样就可以根据能否构成轮换来判断，而发生分叉的地方刚好就是23。
出现如下典型的结构，置s[i] = -1; 然后置s[s[i]],s[s[s[i]]]...
代码大体如下：
#include <stdio.h>
int main(int argc, char *argv[])
{
int i,t,n = 5,temp,head;
int s[6] = {0,1,2,3,4,1,};
for(i = 1 ; i <= n ; i++){
if(s[i] == -1)
continue;
head = temp = i;
while(s[temp] != -1){
t = s[temp];
s[temp] = -1;
temp = t;
}
if(temp != head)
return printf("%d\n",temp);
}
printf("ok\n");
return 0;
}
二分：
数的范围是1-99，以中间值50划分，如无重复，>=50的本应当有50个，<50的本应当有49个，计数发现小于50的有50个，则说明肯定是<50的那部分中有一个重复的，这样就可以减半。以50为中间元进行划分是O(n)的，划分的同时可以计数。二分减半，总的复杂度为O(n)。
利用冗余位，是指在置换监测中，不是让s[i] = -1，而是 s[i] = - s[i]，这样监测完，再让s[i] = -s[i],就恢复原值了，表面上没有增加空间，实际上还是利用了一个冗余的符号位。
评论