题目描述
题解
最简单的方法是设置一个哈希表进行计数，能够方便地寻找到最小值，但是这样需要 \(O(n)\) 的空间去存放哈希表。因此这里提供一种更好的算法（位数统计）能够使空间复杂度降为常数。
由于int类型为32位二进制，于是设置一个长度为32的数组 \(cnt\) 记录数组nums中的每一个数值位出现过多少次1（对所有元素的每个数值位进行统计，而不是统计单个元素的数值位）。再对 \(cnt\) 的每一位做 mod 3 的运算操作，之后就可以得到只出现一次的数字。
考虑样例 [1,1,1,3]，1 和 3 对应的二进制表示分别是 00..001 和 00..011，于是 \(cnt\) 数组为 [0,0,...,1,4]。对每一位进行 mod 3 操作后变为 [0,0,...,1,1]，再转换为十进制就成为了3，即为答案。
需要注意的是，由于普通的int为有符号数，右移操作符为算数右移，与上面描述的算法不相符合（我们需要左边补0，即逻辑右移操作），因此需先将其转为无符号数。
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
vector<int> cnt(32, 0);
for(unsigned x : nums)
{
for(int i = 0; i < 32; i++)
{
if(((x >> i) & 1) == 1)
cnt[i]++;
}
}
int ans = 0;
for(int i = 0; i < 32; i++)
{
cnt[i] %= 3;
if(cnt[i] & 1 == 1)
{
ans += (1 << i);
}
}
return ans;
}
};
时间复杂度为 \(O(n)\)，空间复杂度为 \(O(1)\)
推广一下，如果一个数组中只有一个元素出现了一次而其余元素出现了k次，只需将mod 3 改成 mod k 即可。