Leetcode题解剑指 Offer 56 - I. 数组中数字出现的次数

PROBLEM

难度中等

MY ANSWER

无。

BETTER SOLUTION

先遍历使用异或计算出独立数字a^b，然后找出a^b中一个为1的位，即a和b不相同的一位。用此位将数组分成含a的一组与含b的一组，可知这两组的其他数字都是若干对重复数字。对这两组进行异或，即可得出a与b。时间复杂度O(n)，空间复杂度O(1)。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)         // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)         // 2. 循环左移，计算 m
            m <<= 1;
        for(int num : nums) {       // 3. 遍历 nums 分组
            if(num & m) x ^= num;   // 4. 当 num & m != 0
            else y ^= num;          // 4. 当 num & m == 0
        }
        return vector<int> {x, y};  // 5. 返回出现一次的数字
    }
};。

SUMMARY

注意使用异或来获得若干对重复数字中的独立数字，并根据异或性质进行分组。