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

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

- n2 _6 B7 Y5 j$ [" @% m4 P

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

一、常规解法（3种）

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

1. 
   , Y# K% v; b- l: w/ A( T
2. for（i=0；i＜SIZE；i++）
   
3. {
   
4.     n=0；
   9 D- ~  G5 A3 z
5.     for（j=0；j＜SIZE；j++）
   $ W& `+ E# c5 \; c; T
6.         if（src[i]==src[j]）
   
7.             n++；
   
8.     if (n==3)
   
9.     {
   % M. }" T: @, H! x* T# t+ B8 w2 g
10.         printf（"%d\n",src[i]);
    
11.         return；
    6 T; |1 p2 h+ r$ F8 k: T9 s
12.     }
    3 x: M5 e6 ?; j' d! |
13. }

复制代码

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

1. 
   2 v) N, k  y" P0 R- W! g& X
2. for（i=0；i＜SIZE_src；i++）
   
3.     tmp[src[i]]++; //临时数组tmp
   ; X% h4 G! J- e8 _" I! n
4. for（i=0；i＜SIZE_tmp；i++)
   
5.     if (tmp[i]==3)
   
6.     {
   * e5 y# p( J( D/ s
7.         printf（"%d\n",i）;//打印下标
   
8.         return；
   - x1 U! _$ |) V$ ]; x" |8 P
9.      }
   - G6 C) s- L4 X; A5 C, F

复制代码

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

1. 
   
2. for（i=0；i＜SIZE；i+=2） {
   % W( j' \' o. J
3.     if（src[i]==src[i+1]){
   
4.           if（src[i]==src[i+2]) {
   $ `5 X1 r; t, C% e
5.               printf（"%d\n",i）;
   4 ~! A" S% |  {0 r0 V/ G
6.               return;}}}

复制代码

: z, m$ h* Y- Q, r/ }; K

二、最优解
3 ^/ s3 ]. `8 W. R. @* v: V' X) b

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

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

1. 
   $ R8 Z4 m. z) X7 E3 ?
2. int singlenumber(int src[], int size)
   
3. {
   
4.     int result=0;
   
5.     for(int i=0; i<size; i++)
   & t! c0 p# q: K4 T" E: x4 l2 K8 x
6.         result ^= src[i]; //遍历数组全部异或
   
7.     return result;
   
8. }

复制代码

三、变形推广

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

; N. C' b7 w& j( j/ [* ?8 T8 y( i' D

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

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

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

1. 
   
2. void fun(int src[], int size, int *n1, int *n2)
   5 ^5 r- @: I! j) ^1 q) F+ m
3. {
   6 q; x. r; ^8 _% o; ?
4. int i, j, result;
   3 C  l3 l/ I6 E, V7 u
5. //计算这两个数的异或结果
   # i8 x5 M1 |* H$ d8 r: ^1 r# [
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++)
    3 ?6 ~* j* j0 h2 b) I9 t. h/ g4 E
12. if (((result >> j) & 1) == 1)
    1 i; {" _( d9 T  G3 S7 m" H5 T
13. break;
    
14. // 这两个数字在第j位上是不相同的,由此分组即可
    
15. *n1 = 0, *n2 = 0;
    
16. for (i = 0; i < n; i++){
    3 |; p% u* j# y- f" t
17.      if (((src[i] >> j) & 1) == 0)
    
18.         *n1 ^= src[i];
    
19. else
    9 d4 g7 H' U5 k* m/ L& z" @# _% P
20.     *n2 ^= src[i];
    
21. }}
    

复制代码

  K& \  h# W# y  D, E

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

1. 
   
2. int singlenumber(int src[], int n) {
   % ^, Z5 J' a1 e: L8 t7 V+ M# C
3.       int result = 0;
   
4.       int i, j,sum;
   
5.       for(i=0;i< sizeof(int) * CHAR_BIT;i++)
   9 u+ O! N, M- N5 H4 H9 X, d
6.       {
   
7.           sum = 0;
   ' {* U. `+ C( p$ H( D
8.           for(j=0;j<n;j++)
   3 `5 F. v! n2 ]. q9 z6 d% u+ k1 S$ Y
9.               sum += ((src[j]>>i)&1); //每轮一位做累加
   ) Y" i+ a2 n# T
10.            if(sum%3 == 1)
    - S- V" P$ A* M( x  m
11.            result |= (1<<i);//确定每一位是否为1
    ; e; _8 D' H" r, `  I
12.         }
    
13.         return result;
    
14.     }
    * w' n' g7 I" v9 I

复制代码

四、总结
+ m+ t. F) z% b1 q! Z

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

好题