只出现一次的数字-ii

Tips

题目类型: HashMap, 位运算

相关题目:

• 136. 只出现一次的数字
• 260. 只出现一次的数字 iii

题目

给你一个整数数组 nums, 除某个元素仅出现一次外, 其余每个元素都恰出现三次. 请你找出并返回那个只出现了一次的元素.

• 1 <= nums.length <= 3 * 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1
• nums 中, 除某个元素仅出现一次外, 其余每个元素都恰出现三次

示例

输入: nums = [1, 1, 1, 3]

输出: 3

题解

HashMap 的方式就不说了, 直接看位运算的思路. 因为 -2³¹ <= nums[i] <= 2³¹ - 1, 可以固定 32 位的二进制. 比如示例:

• 1: 00000000000000000000000000000001
• 1: 00000000000000000000000000000001
• 1: 00000000000000000000000000000001
• 3: 00000000000000000000000000000011

然后我们统计每二进制位 1 的个数, 即使用 total += (num >> i) & 1, num >> i 是右移运算符, 比如一开始 i 是 0, 那其实就是统计的最后一位, (num >> 0) & 1 就是最后一位是否为 1. 这样就统计到了 1 的数量为 00000000000000000000000000000014.

接着根据每二进制位 1 个数量, 跟 3 做余数, 如果不为 0, 执行 ans += 1 << i, 1 << i 是左移运算符, 比如一开始 i 是 0, 1 << 0 意味着 1 左移 0 位, 所以还是 1; i 是 1, 1 << 1, 意味着 1 变成了 10, 换算成十进制就是 2. 这样加起来就是 3.

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ans = 0
  for (let i = 0; i < 32; ++i) {
    let total = 0
    for (const num of nums) {
      total += (num >> i) & 1
    }

    if (total % 3 !== 0) {
      ans += 1 << i
    }
  }
  return ans
}