面试题56 - II. 数组中数字出现的次数 II

class Solution {
public:
    int singleNumber(std::vector<int> &nums) 
    {
        if (nums.empty()) 
        {
            return 0;
        }

        // 哈希表存储数和其出现次数
        std::unordered_map<int, int> unorderedMap;
        for (int num : nums) 
        {
            unorderedMap[num]++;
        }

        // 遍历哈希表
        for (auto iter : unorderedMap) 
        {
            // 找到出现次数的数并返回
            if (iter.second == 1) 
            {
                return iter.first;
            }
        }

        return 0;
    }
};

 1 class Solution {
 2 public:
 3     int singleNumber(std::vector<int> &nums) 
 4     {
 5         if (nums.empty()) 
 6         {
 7             return 0;
 8         }
 9 
10         int ans = 0;
11         // 存储所有数字二进制表示的每一位的和
12         int bitSum[32] = {0};
13         // 该位是0或1
14         int bit = 0;
15 
16         // 遍历数组中的数
17         for (int num : nums) 
18         {
19             // 每次更新无符号整数掩码为1
20             unsigned int bitMask = 1;
21             // 对数字的32位进行累加，从低位开始
22             for (int i = 31; i >= 0; i--) 
23             {
24                 // 计算该位是1还是0
25                 bit = num & bitMask;
26                 // 如果不是0，则将存储每位和的数组的该位加1
27                 if (bit != 0) 
28                 {
29                     bitSum[i] += 1;
30                 }
31 
32                 // 将掩码的1左移，接着计算右起开始的下一位
33                 bitMask <<= 1;
34             }
35         }
36 
37         // 遍历二进制每一位和的数组，从高位开始
38         for (int b : bitSum) 
39         {
40             // 考虑到最后一位的情况，
41             // 应该先左移再计算
42             ans <<= 1;
43             // 如果和的该位整除3则为0，
44             // 否则为1
45             ans += (b % 3);
46         }
47 
48         return ans;
49     }
50 };