一个整数数组，每个数字都出现K次，只有一个数字出现M次，找出这个数字（线性时间）

3371 阅读 0 评论 2225 点赞

我是靠谱客的博主炙热自行车，这篇文章主要介绍一个整数数组，每个数字都出现K次，只有一个数字出现M次，找出这个数字（线性时间），现在分享给大家，希望可以做个参考。

原题链接https://leetcode.com/problems/single-number-ii/description/
这类题都是形如给定一个整型数组，数组中每一个数字都出现了K次，只有一个数字出现M次，其中M < K，找到这个数字，要求在线性时间完成且不使用额外的内存空间。

首先考虑K = 2，M = 1的情况，此时可以使用异或运算遍历一遍数组元素，最后异或的结果就是只出现一次的数。因为异或运算具有如下性质：

复制代码

1
2
3
A ^ A = 0;
A ^ A ^ B = B;
A ^ A ^ B = A ^ B ^ A = B ^ A ^ A = B;

所以在遍历的过程中，出现两次的元素都像A ^ A 一样变为0了，最后只留下一个B。

之后考虑把整数看成32bit的二进制数，对于每一个二进制位，异或其实就是如果这个位置出现了两个1，那么就把这个位置变为0。
但是不管出现了多少个1，最后都能组成只出现一次的那个数字，比如说，只出现一次的那个数字是n，n的第7位是1，那么数组中所有元素的第7位计数，一定会有奇数个1，拿出一个1后，剩下的偶数个1彼此异或为0，最后留下的1组成n的第七位。

接下来考虑K > 2的情况，如果K = 3，M = 1或2。此时就不能通过异或直接求得结果，但是异或的思想是二进制位遇到2个1后变为0，利用这个思想，我们可以自己设计一种运算，满足二进制位遇到3个1后变为0，这样再遍历一遍数组元素，剩下的便是要找的出现M次的数字。但是M有1和2两种，怎么区分是出现1次还是出现2次呢，这就需要对M也进行记录，出现1次和出现2次的都需要记录下来。

举个例子，假设int a记录出现1次的数字，int b记录出现2次的数字。从二进制的角度考虑，a的每个二进制位如果是1表示这个二进制位出现1次，相应的b的这个二进制位就是0。b的每个二进制位如果是1表示这个二进制位出现2次，相应的a的这个二进制位就是0。

从二进制的角度考虑，对于32bit中的某一个bit来说
ab的取值为00-01-10-00，
00：这个位置出现0个1或者3个1
10：这个位置出现1个1
01：这个位置出现2个1

用表格的形式表示出现就是：
a：是1表示出现1次
b：是1表示出现2次
c：即将遍历到的数字的该bit
na：改变后的a
nb：改变后的b

复制代码

1
2
3
4
5
6
7
a   b   c   na  nb
0   0   0   0   0
1   0   0   1   0
0   1   0   0   1
0   0   1   1   0
1   0   1   0   1
0   1   1   0   0

所以新定义的运算操作就是让a和b分别为1的运算

复制代码

1
2
3
a   b   c   na  nb
1   0   0   1   0
0   0   1   1   0

na = (a&~b&~c) | (~a&~b&c);

复制代码

1
2
3
a   b   c   na  nb
0   1   0   0   1
1   0   1   0   1

nb = (~a&b&~c) | (a&~b&c);

最后，a表示的是出现1次的数，b表示的是出现两次的数。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0;
        int b = 0;
        for(int c : nums)
        {
            int tmpa = (a&~b&~c) | (~a&~b&c);
            b = (~a&b&~c) | (a&~b&c)
            a = tmpa;
        }


        //return a; //出现1次的数字
        //return b; //出现2次的数字
        return a | b; //不知道是出现1次还是出现2次的数字
    }
};