面试题 56：数组中数字出现的次数.md

（1）试题链接：73. 数组中只出现一次的两个数字 - AcWing题库

方法一：位运算

• 思路：异或运算的性质是两个相同的数异或的结果为 0，因此对数组中的没每个数依次进行异或运算，最后能够得到这两个只出现一次数字的异或结果，由于他们异或的结果中一定有一位二进制下为 1，我们只要将数组中所有这一位为 1 的数异或，就能够得到这两个只出现一次的数字中这一位为 1 的数了，然后再利用异或的性质即可得到另一个数。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int mask = 0;
        for (int num : nums) mask ^= num;
        
        int x = 0;
        int lowbit = mask & -mask;
        
        for (int num : nums) {
            if (lowbit & num) {
                x ^= num;
            }
        }
        
        return {x, mask ^ x};
    }
};

（2）试题链接：74. 数组中唯一只出现一次的数字 - AcWing题库

方法一：计数

• 思路：记录每个二进制位 1 出现的次数，如果某一位 1 出现的次数不是 3 的倍数则它一定是那一个只出现一次的数中的部分。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int cnt[32] = {0};
        
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if (num & (1 << i)) {
                    cnt[i]++;
                }
            }
        }
        
        int ans = 0;
        
        for (int i = 0; i < 32; i++) {
            if (cnt[i] % 3) {
                ans |= 1 << i;
            }
        }
        
        return ans;
    }
};