137. Single Number II

Difficulty:
Related Topics:
Similar Questions:

Problem

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

Solution 1

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  let one = 0;
  let two = 0;
  let len = nums.length;
  for (var i = 0; i < len; i++) {
    one = (one ^ nums[i]) & ~two;
    two = (two ^ nums[i]) & ~one;
  }
  return one;
};

Explain:

one 的二进制中每个 1 代表该位置 1 出现 1 次; two 的二进制中每个 1 代表该位置 1 出现 2 次; 如果某位置 1 出现 3 次,则清零。

Complexity: