剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III

82. 落单的数

给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

样例

给出 [1,2,2,1,3,4,3]，返回 4

典型思考：位运算中的异或运算

 

1、异或

异或运算的性质：

任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果即0与只出现一次的数字异或结果为只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

异或在计算机中运行的机理：其实异或就是把整数的32位的0,1串当做整数0,1，对应位加和后，对2取余的结果，那么对于这样三个数的情况，一样的，可以用相同的方法，对应位的0,1相加，最后对3取余。得到的结果就是那个落单的数的二进制表示。然后恢复成整数即可。

 

 

 

class Solution {
public:
    /**
	 * @param A : an integer array
	 * return : a integer 
	 */
    int singleNumber(vector<int> &A) {
        int x=0;//将x初始化为0，因为0与任何数异或都等于它本身
        for (int i = 0; i < A.size(); i++) {
            x ^= A[i];
        }
        return x;
    }
};

2、异或的机理，利用一个数组记录二进制每个位的和。将所有的数转换成二进制，因为是int类型，共32位。申请常数级（32位）的额外空间，然后每个数对应的位相加，最后对应位上的和模2。最后的结果就是单个数对应的二进制数。

class Solution {
public:
    /**
     * @param A: Array of integers.
     * return: The single number.
     */
    int singleNumber(vector<int> &A) {
        // write your code here
        int ans[32]={0};
       // memset(ans, 0, sizeof(ans));//将ans数组清零
        for(int i=0; i<A.size(); ++i){
            for(int k=0; k<32; k++)
               
         //其中A[i]>>k，意思为A[i]右移k位
        //(A[i]>>k)&1就是读取A[i]>>k的最低位
          ans[k] = (ans[k]+((A[i]>>k)&1))%2;                                            }
        //将结果恢复为整数
        int ret = 0;
        int base = 1;
        for(int i=0; i<32; ++i){
            ret += ans[i]*base;
            base *= 2;
        }
        return ret;
    }
};

 

程序解释：void *memset(void *s, int ch, size_t n); 

 

memset函数解释：将 s 中后 n 个字节 （typedef unsigned int size_t）用 ch 替换并返回 s 。

memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。

例如：要把一个char a[20]清零，一定是 memset(a,0,20);

83. 落单的数 II

给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。

样例

给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4

挑战 

一次遍历，常数级的额外空间复杂度

思想：1、排序，然后再找只出现一次的数。（通过）快排时间复杂度O(nlogn)（每次partition是n，平均需要logn次），空间复杂度O(1)。

2、利用哈希表，这个最简单（通过）

3、利用随机算法，这个也简单(时间超出限制）

4、转换成二进制，同上

代码：快速排序

 

class Solution {
public:
    /*
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
      sort(A.begin(),A.end());
      int count=1,i;
      for(i=1;i<A.size();i++)
      {   
         if(A[i-1]==A[i])
         count++;
         else if(count==1)
         return A[i-1];
         else count=1;
       }
       return A[i-1];
    }
};

2、哈希表

class Solution {
public:
    /*
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
      unordered_map<int,int>result;
      int i;
      for(i=0;i<A.size();i++)
       result[A[i]]++;
      for(i=0;i<A.size();i++)
       if(result[A[i]]==1)
       return A[i];
    }
};

3、随机化方法（时间超出限制）

 

class Solution {
public:
    /*
     * @param A: An integer array
     * @return: An integer
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
       int n=A.size();
       srand(unsigned(time(0)));
        while(true)
        {
            int index=rand()%n;
            int candiate=A[index];
            int count=0;
            for(int i=0;i<n;i++)
            {
                if(A[i]==candiate)
                count++;
            }
            if(count==1)
            return candiate;
        }
    }
};

4、转换成二进制，利用一个数组记录二进制每个位的和

 

class Solution {
public:
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
       
        int ans[32];
        memset(ans, 0, sizeof(ans));
        for(int i=0; i<A.size(); ++i){
            for(int k=0; k<32; k++)
                ans[k] = (ans[k]+((A[i]>>k)&1))%3;
        }
         
        int ret = 0;
        int base = 1;
        for(int i=0; i<32; ++i){
            ret += ans[i]*base;
            base *= 2;
        }
        return ret;
    }
};

 
总结：上述四种方法，比较看来，哈希表更通用一些，且简单，转换二进制对这种题型通用，随机化方法次之（但容易超出时间限制），排序方法次之。

84. 落单的数 III

 

异或应用升级版：

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：这是一道很新颖的关于位运算的面试题。

首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。

分组依据：对于2*n+1个数字用异或就行了，而在此题将所有数异或之后得到的是两个落单的数的异或结果，没办法将结果拆分成两个落单的数。但因为两个落单数不同，所以肯定存在某个位k，使得两落单数在第k位上一个为0另一个为1，怎么找到这个k? 找异或结果中1出现的位置即可。只需找到最小的这个k，然后将在k位上为0的所有数做异或，其他的在k位为1的所有数也做另外的异或，这样最终可以得到两个落单的数。

 

解决方案

 

　　　　　　

上图将所有二进制数按照第3位是否为1分成两组。

现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。

基于上述思路，我们不难写出如下代码：

 

1. class Solution {  
2. public:  
3.     /** 
4.      * @param A : An integer array 
5.      * @return : Two integers 
6.      */  
7.     vector<int> singleNumberIII(vector<int> &A) {  
8.         // write your code here  
9.         //求出Xor
10.         int Xor = 0, n = A.size();  
11.         for ( int i = 0; i < n; ++i ) Xor ^= A[i];  
12.         int k = 0;  
13.        //通过移位找到二进制Xor中最小的1
14.         while ( Xor % 2 == 0 )  
15.         {  
16.             ++k;  
17.             Xor >>= 1;  
18.         }  
19.        //对各数进行分组计算
20.         int r1 = 0, r2 = 0;  
21.         for ( int i = 0; i < n; ++i )  
22.         {  
23.             int kb = (A[i]>>k) % 2;  
24.             if ( kb == 0 ) r1 ^= A[i];  
25.             else r2 ^= A[i];  
26.         }  
27.       //将结果压入res数组中 
28.         vector<int> res;  
29.         res.push_back(r1);  
30.         res.push_back(r2);  
31.         return res;  
32.     }  
33. };