Microsoft : 找出唯一重复的数

There is an array of size 50 that is expected to contain all the numbers from 1 to 50
(every number occuring only once). But there is one number in the array that does not
satisfy this condition i.e. one number is either duplicate or outside 1 to 50 range.
Find the correct number that is missing in the array.. O(n) soln required.

将该数组所有的数xor起来，记为A
将1~50所有的数xor起来，记为B
A xor B即是结果

回复 2# epic
不是吧，这样相同的两两抵消之后得到的应该是missing的数和多余的数xor在一起的结果啊，怎么分离这两个数呢

回复 3# darksteel

1. int findMissing(int a[], int n)
   
2. {
   
3.         int i;
   
4.         for(i = 0; i < n; i++) {
   
5.                 while(a[i] >= 1 && a[i] <= n && a[a[i] - 1] != a[i])
   
6.                         swap(a[i], a[a[i] - 1]);
   
7.         }
   
8.         for(i = 0; i < n; i++)
   
9.                 if(a[i] != i + 1)
   
10.                         return i + 1;
    
11.         return -1;
    
12. }

复制代码

回复 3# darksteel

你说的对，我没看清题……

重新来，如果我没理解错的话，题意说有一个数要么出现了2次，要么它不属于[1,50]。

那就……
循环一遍，看有没有>50或者<1的数，若有，得到答案，若无，按上一个做法……

回复 5# epic
题目要得到的是missing的那个数好像。。如果有一个数在1到50之外，那可以找出来，然后用上面你的方法可以分离出missing的数，如果有一个数重复，那就不好办了。你上面的方法得到的是missing的数和duplicate的xor的结果，duplicate可能是1-50任意一个数，这就不好分离了吧

回复  darksteel
darksteel 发表于 2011-7-29 12:14

    这个因该是对的,xor不容易解决这个问题.
贴一下我的:

1. 
   
2. int FindDup(int a[], int n)
   
3. {
   
4.         assert(a && n > 0);
   
5. 
   
6.         for (int i = 0; i < n; i++)
   
7.         {
   
8.                 if (i + 1 == a[i])
   
9.                         continue;
   
10. 
    
11.                 int nTmp = a[i];
    
12.                 while (i + 1 != nTmp)
    
13.                 {
    
14.                         if (nTmp < 1 || nTmp > n)
    
15.                                 return -1;
    
16. 
    
17.                         if (nTmp == a[nTmp - 1])
    
18.                                 return nTmp;
    
19. 
    
20.                         int x = a[nTmp - 1];
    
21.                         a[nTmp - 1] = nTmp;
    
22.                         nTmp = x;
    
23.                 }
    
24.         }
    
25. 
    
26.         return -1;
    
27. }
    

复制代码