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

题意：

给定一个整数数组和整数 $k$ ，其中数组中有一个数只出现一次，其他数都出现 $k$ 次，求这个只出现一次的数。

方法一：

解题思路：

在 $k$ 为偶数时，将所有数异或就能得到答案，因为偶数个相同数异或结果为 $0$ ，最终只留下了要求的数，时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。
在 $k$ 为奇数时，若利用计数的方式来求答案，那么空间复杂度会来到 $O(n)$ ，不满足题目要求。由于题目要求时间复杂度 $O(32n)$ ，空间复杂度 $O(1)$ 。所以选择采用位运算的方式，即计算所有数在每一位的1的数目，再将该数模 $k$ ，最后再复原得到答案。由于int数组最多32位，所以时间复杂度是 $O(32)*O(n)=O(32n)$ ，空间复杂度是 $O(1)$ ，满足要求。

图解如下：

图片说明

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr intvector 
     * @param k int 
     * @return int
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        // write code here
        int ans = 0;
        //如果k是偶数，那么直接将全部数异或一次就能得到答案
        if (k % 2 == 0) {
            for (int x : arr) {
                ans = ans ^ x;
            }
        }
        //k是奇数
        else {
            //计算每一位上面的1的数目并存储下来
            vector<int> sum(32,0);
            for (int i = 0; i < 32; i++) {
                for (int x : arr) {
                    sum[i] += (x >> i) & 1;
                }
            }
            //将每个位置上的1的数目模k，若还有余数，说明要求的数在该位为1，加到ans中
            for (int i = 0; i < 32; i++) {
                if (sum[i] % k != 0) {
                    ans += 1 << i;
                }
            }       
        }
        return ans;
    }
};

复杂度分析：

时间复杂度： $O(32n)$ ，双重循环，外层32，内层n，总 $O(32n)$ 。
空间复杂度： $O(1)$ ，sum数组，常数级， $O(1)$ 。