Ex56-II 数组中数字出现的次数II

题目描述

在一个数组 nums中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

解题思路

把数组中数字的每一个（二进制）位相加（十进制），得到的数如果能被3整除，则说明那个只出现一次的数字在这一位上是0，反之，其在这一位上是1。

代码

class Solution {
 public:
  int singleNumber(std::vector<int>& nums) {
    constexpr int INT_BIT_SIZE = sizeof(int) * 8;
    std::vector<int> bits(INT_BIT_SIZE, 0);
    for (int i = 0; i < nums.size(); ++i) {
      int j = bits.size() - 1;
      int num = nums[i];
      while (num) {
        bits[j] += (num & 1);
        num >>= 1;
        --j;
      }
    }
    int res = 0;
    for (int i = bits.size() - 1; i >= 0; --i) {
      res += (1 << (INT_BIT_SIZE - i - 1)) * (bits[i] % 3);
    }
    return res;
  }
};

结果

执行结果：通过

执行用时：60 ms, 在所有 C++ 提交中击败了91.09%的用户

内存消耗：16.3 MB, 在所有 C++ 提交中击败了37.39%的用户