MS/Google面试题：寻找丢失的数字



MS/Google面试题：寻找丢失的数字，

题目：

有一组数字，从1到N，其中丢失了一个数字，且顺序也被打乱的存储在一个 size 为N-1的数组中

要求：

找出丢失的数字，最好能有程序，最好算法比较快

BTW1：有很多种方法哦，据说O(n)的方法不止一种

BTW2：扩展问题，如果丢失两个，并找出这两个数字；或者，丢失三个，找出三个中的任意一个数字即可

BTW3：一定要小心溢出哦

BTW4：最好不要多申请 N 多空间

题目：

1、给你n个数，其中有且仅有一个数出现奇数次，其余的数都出现偶数次。要求用线性时间常数空间找出出现奇数次的那个数。

2、同样是n个数，其中有且仅有2个数出现奇数次，其余都出现偶数次。要求用线性时间常数空间找出出现奇数次的两个数。

 

题目1 ：

分析如下：


如果我们采用 两次for循环来一一比较的话，当然可以解出来，但是时间复杂度为O(n^2)；现在如何在线性时间内解决出此题呢？我们可以观察到，这个数组中所有的数据都是出现偶数次，只有一个数是出现奇数次，到这里我们就应该想到：如果把偶数次的数能够两两成对消掉剩下的就是出现奇数次的那个数了，这是解题的突破口；找到这个突破口之后，我们如何来消掉成对的数呢？我们很容易想到 相加 相减 ，比如 A+B-A-B ；但是由于现在数组是无序的，加减也是无规律的，而且我们不能对其排序，这样就不是线性时间了，那么还有没有其他的消掉相同数据的运算呢？这时候我们就应该想到 异或运算了，对于A^B^A^B^C = C ；这时就可以求出唯一出现奇数次的数据 C 了，这里说明下：异或运算 遵守交换率，所以A^B^A^B^C = A^A^B^B^C =C；这样我们就很容易求出数组中出现奇数次的那个数据了，一次遍历即可，代码实现如下：

 

  1. #include <iostream>
  2. using namespace std;
  3. #define N 7
  5. int arr[7] = {1 ,2,3,1,3,2,8};
  6. int findSingleNum()
  7. {
  8.     int i;
  9.     int res;
  10.     for(i=0 , res=0 ;i<N;i++)
  11.         res ^=arr[i];
  12.     return res;
  13. }
  15. int main()
  16. {
  17.     cout << ”Hello world!” << endl;
  18.     cout<<findSingleNum()<<endl;
  19.     return 0;
  20. }

运行结果：

 

 

 

题目2：

题目2是题目1的拓展，假如说现在出现奇数次的个数为2个数据，那么如何求出这两个数据；要求同样是线性时间复杂度和常数空间复杂度。很显然，必须坚持用 异或运算来解题。分析：设数组 Array 中两个出现奇数次的数据分别为 ：S1 、S2，当我们遍历一遍之后，结果 res = S1^S2 ，因为S1 != S2，所以 res 肯定不等于 0 ；res的二进制表示形式中至少有1位为 1 ；这样又出现了解题的突破口，现在我们如何来利用这个 位 1 呢？

分析如下：为了更加形象化，现在我们就拿 S1=7  S2=4 来分析，res = 3 ，二进制表示形式为：res = 11 ；我们现在知道res的二进制表示形式中必然有1，我们只需找到一个 1 即可，此时我们选择第1位(从右往左数)的1；接下来来考虑，对于数组Array中的每一个数，其二进制表示形式的最低位有两种选择 0 或 1；解释这个目的就是为了将 S1 、S2分在两组中来考虑！因为 S1^S2 最低位为1，所以 S1、S2  最低位不同，可以分在两组中，同时对于数组中其他的数，要么是成对的出现在 最低位为1的组中，要么是出现在最低位为0的组中，对其中一个组的数据分析，即可求出其中的一个数 S1； 那么我们已经知道了 res = S1^S2 ，且计算除了S1的值，那么 S2 =S1^S1^S2 ，得解。

代码如下：

 

  1. #include <iostream>
  2. using namespace std;
  3. #define N 8
  5. int arr[N] = {1 ,2,3,1,3,2,8,9};
  7. int findlowone(int res)
  8. {
  9.     int countt = 0;
  10.     int k = 1;
  11.     while( res&k == 0)
  12.         k=k<<1,countt++;
  13.     return countt;
  14. }
  15. void findSingleNum(int &s1,int &s2)
  16. {
  17.     int i;
  18.     int res;    //res = s1^s2
  19.     for(i=0 , res=0 ;i<N;i++)
  20.         res ^=arr[i];
  22.     //找出res中 最低位的 1 的位置
  23.     int k = findlowone(res);
  24.     k=1<<k; //将1左移k位
  26.     for(i=0,s1=0;i<N;i++)
  27.     {
  28.         if(arr[i]&k)    //如果这位为1 ，说明该数据在 s1 所在的组中，进行异或运算
  29.             s1 ^=arr[i];
  30.     }
  31.     s2 = s1^res;
  32. }
  34. int main()
  35. {
  36.     cout << ”Hello world!” << endl;
  37.     int s1,s2;
  38.     findSingleNum(s1,s2);
  39.     cout<<s1<<endl<<s2<<endl;
  40.     return 0;
  41. }

运行结果：