137. 只出现一次的数字 II

137. 只出现一次的数字 II

题目描述

题解

最简单的方法是设置一个哈希表进行计数，能够方便地寻找到最小值，但是这样需要 \(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 即可。