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

思路：

题目的主要信息：

• 数组有n个无序数字，其中有一个数字只出现了1次，其他数字都出现了k次
• 需要找到只出现了一次的数字
• k>1，k无特殊情况，只需要考虑空数组

方法一：排序法
具体做法：
首先对数字进行排序，使之呈现递增的状态，这样相同的数字必然相邻。因为其他数字至少出现大于1次，因此首尾如果与旁边不同则刚好是首尾，如果是在中间则需要比较是否与前后都不同才行，如此遍历一次即可。

class Solution {
public:
    int foundOnceNumber(vector<int>& arr, int k) {
         if(arr.size() == 0)
             return 0;
        sort(arr.begin(), arr.end()); //排序法
        //因为其他数字至少出现大于1次，因此首尾如果与旁边不同则刚好是首尾
        if(arr[0] != arr[1])
            return arr[0];  
        else if(arr[arr.size() - 1] != arr[arr.size() - 2])
            return arr[arr.size() - 1];
        for(int i = 1; i < arr.size() - 1; i++){
            if(arr[i] != arr[i - 1] && arr[i] != arr[i + 1]) //中间需要比较前后两个
                return arr[i];
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：，排序的复杂度为，遍历一次为
• 空间复杂度：，无额外使用空间

方法二：哈希表
具体做法：
建立一个哈希表，key值表示数字，value值表示数字出现的次数，统计完数组中所有数字后，遍历哈希表，找到value为1的key值。

class Solution {
public:
    int foundOnceNumber(vector<int>& arr, int k) {
        map<int, int> mp;  //哈希表统计数字出现的次数
        for(int i = 0; i < arr.size(); i++){
            if(mp.find(arr[i]) != mp.end())
                mp[arr[i]]++;  //多次出现则增加
            else
                mp[arr[i]] = 1; //首次出现
        }
        for(auto iter = mp.begin(); iter != mp.end(); iter++){ //遍历哈希表找到出现一次的数字
            if(iter->second == 1)
                return iter->first;
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：，统计数字是，遍历哈希表是
• 空间复杂度：，哈希表的大小，一共有种元素

方法三：位运算
具体做法：
我们用一个32个元素的数组来记录所有数字中二进制1的个数，因为其他每个数字出现k次，因此如果数组中没有只出现一次的数，全部都出现k次，我们可以发现，32位数组中单独每个元素模k都等于0，因为刚好都是k的倍数。如果加上只出现一次的数，那么模k就只剩下只出现一次的数的二进制中1的个数，再将其转换成十进制即可。

class Solution {
public:
    int foundOnceNumber(vector<int>& arr, int k) {
        vector<int> dp(32, 0);  //保存所有数字二进制中1的个数
        int res = 0;
        for(int i = 0; i < arr.size(); i++){ 
            for(int j = 0; j < 32; j++){
                if((arr[i] >> j) & 1)
                    dp[j]++;
            }
        }
        for(int i = 0; i < 32; i++){
            if((dp[i] % k) & 1)  //模k还剩下1的
                res += 1 << i; 
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历一次数组，再遍历一次32个的辅助数组
• 空间复杂度：，辅助数组dp是常数空间