137. Single Number II

发表于 | 分类于

每日一题 2019 - 05 - 06

题目：

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,3,2]
Output: 3

Example 2:

1
2
Input: [0,1,0,1,0,1,99]
Output: 99

解法：

这个题让找出给定的数组中只出现一次的数据，如果使用排序的话，也可以解决问题，只要在排序中找到与前后都不相同的数据返回即可，这样的话时间复杂度大概是 o(nlogn)，但是为了达到时间复杂度 o(n)，也即保证搜索时间是线性的，还需要进一步改进算法；

参考网上大神的算法，思路如下：

数组为[2,2,2,3]，一共有四个元素，进行四次循环。

第一次循环，b=(0000^0010)&1111=0010=2，a=(0000^0010)&1101=0000=0

第二次循环，b=(0010^0010)&1111=0000=0，a=(0000^0010)&1111=0010=2

第三次循环，b=(0000^0010)&1101=0000=0，a=(0010^0010)&1111=0000=0

第四次循环，b=(0000^0011)&1111=0011=3，a=(0000^0011)&1100=0000=0

不知道大家有没有发现，某个值nums[i]第一次出现的时候，b把它记录了下来，这时候a=0；接着第二次出现的时候，b被清空了，记录到了a里面；接着第三次出现的时候，b和a都被清空了。

如果一个数组中，所有的元素除了一个特殊的只出现一次，其他都出现了三次，那么根据我们刚刚观察到的结论，最后这个特殊元素必定会被记录在b中。

有些朋友会说，但是不一定数组都是刚好3个2都在一起，3个4都在一起，都能够满足刚刚这样子的做法。

上上篇博客136题中，笔者本人提出了异或其实是满足交换律和结合律的，而且&这个操作也是满足交换律和结合律的，所以无论3个2会不会一起出现，结果都是会刚好抵消的。

所以上述的方法可以解决这个问题。

代码：

1
2
3
4
5
6
7
8
9
10
int singleNumber(vector<int>& nums) 
{
    int a = 0, b = 0;
    for (int i = 0; i < nums.size(); ++i) 
    {
        b = (b ^ nums[i]) & ~a;
        a = (a ^ nums[i]) & ~b;
    } 
    return b;
}
0%
undefined