大家好，昨天和同事聊到了一个比较有意思的C语言面试题，感觉还不错，拿出来与大家分享一下，记得在以前的推文中我们写过此类问题，此题确实较为经典，我们也对它进行了一定的变形总结推广，希望对大家有所帮助，请看题：

题目是这样的：在一个整数数组中1个数出现了3次，其余的数都出现了2次，请找出出现3次的数。

建议大家自己先思考一下，我们下面直接给出了解法。

一、常规解法（3种）

1.用两个循环，外层循环每次提供一个数，内层循环遍历数组进行比对，用另外的变量存储相等的次数，内层循环结束之后，如果存储次数的变量等于3，就输出这个元素，然后退出，否则外层循环提供下一个值，继续上述过程。

1. 
   
2. for（i=0；i＜SIZE；i++）
   
3. {
   
4.     n=0；
   
5.     for（j=0；j＜SIZE；j++）
   
6.         if（src[i]==src[j]）
   
7.             n++；
   
8.     if (n==3)
   
9.     {
   
10.         printf（"%d\n",src[i]);
    
11.         return；
    
12.     }
    
13. }

复制代码

2. 建立一个临时数组，初始化为0，遍历一遍题目所给数组，将数组对应的值记录到新数组中，出现一次就++，所给数组的值和新数组的下标一一对应，然后遍历新数组，读出记录的值。

1. 
   
2. for（i=0；i＜SIZE_src；i++）
   
3.     tmp[src[i]]++; //临时数组tmp
   
4. for（i=0；i＜SIZE_tmp；i++)
   
5.     if (tmp[i]==3)
   
6.     {
   
7.         printf（"%d\n",i）;//打印下标
   
8.         return；
   
9.      }
   

复制代码

3. 先用快排排序，再遍历数组，如果第i个数组元素与第i+1个相同就i+2,如果i与i+1，i+2都相同，就输出，否则继续下一轮循环。

1. 
   
2. for（i=0；i＜SIZE；i+=2） {
   
3.     if（src[i]==src[i+1]){
   
4.           if（src[i]==src[i+2]) {
   
5.               printf（"%d\n",i）;
   
6.               return;}}}

复制代码

二、最优解

以上3种方法无疑都是可行的，但都不是最优解，有的时间复杂度有问题，有的无法估计边界，有的代码太复杂，也不是我们今天想讲的。其实本题采用位运算中异或是最简单的。

讲之前要明确几个知识点：（1）整数与0异或为本身。与本身异或为0，即本身的奇数次异或还为本身，偶数次异或为0。（2）异或运算符合结合律和交换律。有了以上两点，本题很简单了，全部异或后，出现2次数的异或都为0，只剩出现3次的数了。

1. 
   
2. int singlenumber(int src[], int size)
   
3. {
   
4.     int result=0;
   
5.     for(int i=0; i<size; i++)
   
6.         result ^= src[i]; //遍历数组全部异或
   
7.     return result;
   
8. }

复制代码

三、变形推广

看到这里，本题就可推广为一个数出现了奇数次，其他数全为偶数次，找出该数，以上代码依旧没有问题。其实还可以有很多经典变形，都是利用位运算解决，但难度有所提高。请看如下两个变形：

（1）若有两个数出现了1次，其他数出现了2次，找出这两个数。（原百度面试题）

（2）若有一个数出现了1次，其他数出现了3次，找出这个数。

我们先看第一题：现在数组中有两个数字只出现1次，直接异或一次只能得到这两个数字的异或结果，但光从这个结果肯定无法得到这个两个数字。如果能将两个数分开到二个数组中，那显然符合上述“异或”解法的关键点了。因此这个题目的关键点就是将这两个数分开到二个数组中。由于在二进制上必定有一位是不同的。我们只需找出第一位不同的就行，这根据异或的结果就可以知道了，这个结果在二进制上为1的位都说明这两个数在这一位上是不同的。

1. 
   
2. void fun(int src[], int size, int *n1, int *n2)
   
3. {
   
4. int i, j, result;
   
5. //计算这两个数的异或结果
   
6. result = 0;
   
7. for (i = 0; i < size; i++)
   
8. result ^= src[i];
   
9. 
   
10. // 找第一个为1的位
    
11. for (j = 0; j < sizeof(int) * CHAR_BIT; j++)
    
12. if (((result >> j) & 1) == 1)
    
13. break;
    
14. // 这两个数字在第j位上是不相同的,由此分组即可
    
15. *n1 = 0, *n2 = 0;
    
16. for (i = 0; i < n; i++){
    
17.      if (((src[i] >> j) & 1) == 0)
    
18.         *n1 ^= src[i];
    
19. else
    
20.     *n2 ^= src[i];
    
21. }}
    

复制代码

再来看第二题：假如二进制位不进位的话，对数组中除了那个数以外的所有数做累加，每一位上的值都是3的倍数。而在加上这个数后，每一位取模3后，不是1就是0，组合起来就是该数了。（当然还有更好的解法，能进一步降低时间复杂度，用到了类似于逻辑电路的相关知识，难度又有所增加，在这里就不讲了）

1. 
   
2. int singlenumber(int src[], int n) {
   
3.       int result = 0;
   
4.       int i, j,sum;
   
5.       for(i=0;i< sizeof(int) * CHAR_BIT;i++)
   
6.       {
   
7.           sum = 0;
   
8.           for(j=0;j<n;j++)
   
9.               sum += ((src[j]>>i)&1); //每轮一位做累加
   
10.            if(sum%3 == 1)
    
11.            result |= (1<<i);//确定每一位是否为1
    
12.         }
    
13.         return result;
    
14.     }
    

复制代码

四、总结

各位，今天我们讲的题目可以总称为“寻找出现N次的数”，最本质最核心的其实就是位运算的灵活运用，再怎么变换，到了最后都是巧用位运算，这也是这类题最终想考察的知识点，希望今天的文章对大家有所启发、有所帮助，就到这里吧，感谢耐心阅读。

好题