260. Single Number III 260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

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

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity? 260. Single Number III

---

本题是LeetCode Single Number的升级版，即数组中有两个只出现一次的数，其他的数都出现了两次，现在要把这两个只出现一次的数找出来。
直接用LeetCode Single Number异或的方法是不行的，因为虽然出现两次的数异或等于0了，但是有两个只出现一次的数a和b，得到的结果是它们的异或a^b。
如果有办法把数组中的数分成两堆，a和b在不同的堆里，并且每堆除了a或b，其他数也都恰好出现了两次，即如果3出现两次，则两个3要么都在a堆中，要么都在b堆中。这样我们就可以对两个堆分别异或，找到每堆中只出现一次的数a和b。
那么根据a^b的结果能否把数分成两堆呢，答案是可以的。异或的规则是相同为0，不同为1。既然a和b分别只出现了1次，那么a和b肯定是不同的两个数，所以他们的异或结果的二进制中肯定有一位是1，记这一位为x，那么a和b在x位的二进制肯定是不一样的，这就找到了a和b的区别。
所以我们可以把数组中的所有数按x位为0或1分成两堆，这样就达到了开头的目的，然后利用LeetCode Single Number的方法，在两堆进行异或，最终就能找到a和b了。完整代码如下：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int flag = 0;
        for (int i = 0; i < nums.size(); ++i) {
            flag ^= nums[i];
        }
        int mask = 1;
        for (int i = 0; i < 32; ++i) {
            if ((flag & mask) != 0)
                break;
            mask <<= 1;
        }
        vector<int> ans(2, 0);
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] & mask) {
                ans[0] ^= nums[i];
            }
            else {
                ans[1] ^= nums[i];
            }
        }
        return ans;
    }
};

本代码提交AC，用时16MS。

二刷。相同思路，很简洁的代码，对于n，直接n&(-n)就能得到其最后一位1的位置，请看面试笔试宝典第三版P97，代码如下：

class Solution {
public:
	vector<int> singleNumber(vector<int>& nums) {
		int c = 0, n = nums.size();
		for (int i = 0; i < n; ++i) {
			c ^= nums[i];
		}
		c = c & (-c); // 得到c最后一个1
		int a = 0, b = 0;
		for (int i = 0; i < n; ++i) {
			if ((nums[i] & c) == 0) { // 注意加括号，位运算优先级低于==
				a ^= nums[i];
			}
			else {
				b ^= nums[i];
			}
		}
		return { a,b };
	}
};

本代码提交AC，用时20MS。