/*
    给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
    示例 1：
    输入：nums = [2,2,3,2]
    输出：3
    示例 2：
    输入：nums = [0,1,0,1,0,1,99]
    输出：99
    */

    1. #include <iostream>
    2. #include <vector>
    3. #include <set>
    4. #include <map>
    6. using std::vector;
    7. using  std::set;
    8. using std::map;
    9. #if 0  //使用hashSet
    10. int singleNumber(vector<int>& nums) {
    11.     int sum = 0, sum1 = 0;;
    12.     set<int> si;
    13.     for (int num : nums)
    14.     {
    15.         si.insert(num);
    16.         sum += num;
    17.     }
    18.     for (int k : si)
    19.     {
    20.         sum1 += k;
    21.     }
    22.     return (3 * sum1 - sum) / 2;
    23. }
    24. #endif
    25. #if 0
    26. int singleNumber(vector<int>& nums) {
    27.     map<int, int> mii;
    28.     for (int num : nums)
    29.     {
    30.         mii[num]++;
    31.     }
    32.     for (auto i = mii.begin(); i != mii.end(); i++)
    33.     {
    34.         if (i->second == 1)
    35.         {
    36.             return i->first;
    37.         }
    39.     }
    40.     return 0;
    41. }
    42. #endif
    43. int singleNumber(vector<int>& nums) {
    45.     int ans = 0;
    46.     for (int i = 0; i < 32; ++i)
    47.     {
    48.         int total = 0;
    49.         for (int num : nums)
    50.         {
    51.             total += ((num >> i) & 1);  //对于数组中的每一个元素 xx，我们使用位运算 \texttt{(x >> i) \& 1}(x >> i) & 1 得到 xx 的第 ii 个二进制位，并将它们相加再对 33 取余，得到的结果一定为 00 或 11，即为答案的第 ii 个二进制位
    53.         }
    54.         if (total % 3)
    55.             ans |= (1 << i);
    56.     }
    57.     return ans;
    58. }
    60. int main()      
    61. {
    62.     vector<int>nums{ 0,1,0,1,0,1,99 };
    63.     std::cout<<singleNumber(nums);
    65. }