【Leetcode】137. Single Number II（经典）（异或运算）（2019年美团无人驾驶算法实习面试原题）

川长思鸟来 2022-02-09 10:37 290阅读 0赞

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:**

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

**Example 2:**

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

题目大意：

给出一个数组，其中只有一个数的出现次数不满足三次，找出这个数。

解题思路:

第136题是找出只出现一次的，我们只使用一个参数即可记录最终结果。因为此时只有两种情况，即a=x或a=0。

拓展到三次的时候就会有三种情况，即0次（三次抵消）、出现一次、出现两次。那么我们就需要使用两个参数来记录。  
当5第一次出现的时候，b = 5, a=0, b记录这个数字  
当5第二次出现的时候，b = 0, a=5， a记录了这个数字  
当5第三次出现的时候，b = 0, a=0， 都清空了，可以去处理其他数字了  
所以，如果有某个数字出现了1次，就存在b中，出现了两次，就存在a中，所以返回 a|b

公式方面 ，上面两次的时候，b清空的公式是 b = b xor i；而第三次时，b要等于零，而这时a是True，所以再 & 一个a的非就可以，b = b xor & ~a  
\-> b = b xor i & ~ a  
a = a xor i & ~b

class Solution {
    public:
        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;
        }
    };