思路：
题目的主要信息：
- 数组有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;
}
};复杂度分析：
- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号