题解 | #数组中只出现一次的数（其它数出现k次）#

NC156 数组中只出现一次的数（其它数出现k次）

题意

给你一个int数组，有一个数只出现1次，其他数都出现k次，求这个出现一次的数。

1. 暴力法

二重循环，每遍历一个数，就找这个数出现了几次，如果是1次，则返回之。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        for (auto a : arr) {
            int times = 0;
            for (auto b : arr) 
                // 如果这个数在数组中出现了，记1次
                if (a == b)
                    times++;


            // 如果出现的次数恰好是1次，那就返回他
            if (times == 1) return a;
        }
        // 占位，因为已知条件中说这样的数必定存在，这个分支无意义
        return 0;
    }
};

时间复杂度: $O(n^2)$ , 两重循环
空间复杂度: $O(1)$

2. 哈希表法

定义一个哈希表，key为arr中的整数，value为它出现的次数。遍历完数组后再遍历哈希表，找value为1对应的key。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        unordered_map<int, int> m;
        for (auto a : arr) 
            m[a]++;

        for (auto [k, v] : m) {
            if (v == 1)
                return k;
        }
        return 0;
    }
};

时间复杂度: $O(n)$ , 哈希表的查找和添加近似看做 $O(1)$ .
空间复杂度: $O(n)$ 定义了跟数组长度成线性关系的哈希表m。

3. 位运算法

考虑k=2的情况，我们可以把所有数全异或得到答案。对于更一般的k，我们可以借助异或的规律，这样解决本题：

把每个数按二进制位拆开，统计整个数组中，每一位中1出现的次数。
如果一个数出现了k次，那么每一位中1出现的次数都是k，所以这k个数的1出现次数模k为0
而剩下的数同样计算，模k为1.

用下图描述上面的关系（图中为了便于叙述，数组是有序的，但是无序也没关系）：

图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        int sum = 0;
        // 都是int类型，所以不超过32位
        for (int i = 0; i < 32; i++) {
            int temp = 0;
            for (auto a : arr) 
                temp += (a >> i) & 1; // 记录下第i位中1出现的个数

            // 如果模k不为0，说明答案的第i就是1
            if (temp % k) 
                sum += (1<<i);
        }
        return sum;
    }
};

时间复杂度: $O(32n)$ , 外层循环32次(常数)，内层循环 $n$ 次
空间复杂度: $O(1)$ 定义了常数个变量。