Question

137. 只出现一次的数字 II

English Version

题目描述

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

 

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

 

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

解法

方法一：位运算

我们可以枚举每个二进制位 $i$，对于每个二进制位，我们统计所有数字在该二进制位上的和，如果该二进制位上的和能被 $3$ 整除，那么只出现一次的数字在该二进制位上为 $0$，否则为 $1$。

时间复杂度 $O(n \times \log M)$，空间复杂度 $O(1)$。其中 $n$ 和 $M$ 分别是数组的长度和数组中元素的范围。

class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    ans = 0
    for i in range(32):
      cnt = sum(num >> i & 1 for num in nums)
      if cnt % 3:
        if i == 31:
          ans -= 1 << i
        else:
          ans |= 1 << i
    return ans

class Solution {
  public int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
      int cnt = 0;
      for (int num : nums) {
        cnt += num >> i & 1;
      }
      cnt %= 3;
      ans |= cnt << i;
    }
    return ans;
  }
}

class Solution {
public:
  int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
      int cnt = 0;
      for (int num : nums) {
        cnt += ((num >> i) & 1);
      }
      cnt %= 3;
      ans |= cnt << i;
    }
    return ans;
  }
};

func singleNumber(nums []int) int {
  ans := int32(0)
  for i := 0; i < 32; i++ {
    cnt := int32(0)
    for _, num := range nums {
      cnt += int32(num) >> i & 1
    }
    cnt %= 3
    ans |= cnt << i
  }
  return int(ans)
}

function singleNumber(nums: number[]): number {
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    const count = nums.reduce((r, v) => r + ((v >> i) & 1), 0);
    ans |= count % 3 << i;
  }
  return ans;
}

impl Solution {
  pub fn single_number(nums: Vec<i32>) -> i32 {
    let mut ans = 0;
    for i in 0..32 {
      let count = nums
        .iter()
        .map(|v| (v >> i) & 1)
        .sum::<i32>();
      ans |= count % 3 << i;
    }
    ans
  }
}

int singleNumber(int* nums, int numsSize) {
  int ans = 0;
  for (int i = 0; i < 32; i++) {
    int count = 0;
    for (int j = 0; j < numsSize; j++) {
      if (nums[j] >> i & 1) {
        count++;
      }
    }
    ans |= (uint) (count % 3) << i;
  }
  return ans;
}

class Solution {
  func singleNumber(_ nums: [Int]) -> Int {
    var a = nums.sorted()
    var n = a.count
    for i in stride(from: 0, through: n - 2, by: 3) {
      if a[i] != a[i + 1] {
        return a[i]
      }
    }
    return a[n - 1]
  }
}

方法二：数字电路

我们考虑一种更高效的方法，该方法使用数字电路来模拟上述的位运算。

一个整数的每个二进制位是 $0$ 或 $1$，只能表示 $2$ 种状态。但我们需要表示当前遍历过的所有整数的第 $i$ 位之和模 $3$ 的结果，因此，我们可以使用 $a$ 和 $b$ 两个整数来表示。那么会有以下三种情况：

1. 整数 $a$ 的第 $i$ 位为 $0$ 且整数 $b$ 的第 $i$ 位为 $0$，表示模 $3$ 结果是 $0$；
2. 整数 $a$ 的第 $i$ 位为 $0$ 且整数 $b$ 的第 $i$ 位为 $1$，表示模 $3$ 结果是 $1$；
3. 整数 $a$ 的第 $i$ 位为 $1$ 且整数 $b$ 的第 $i$ 位为 $0$，表示模 $3$ 结果是 $2$。

我们用整数 $c$ 表示当前要读入的数，那么有以下真值表：

$a_i$	$b_i$	$c_i$	新的 $a_i$	新的 $b_i$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	0	0

基于以上真值表，我们可以写出逻辑表达式：

$$ a_i = a_i' b_i c_i + a_i b_i' c_i' $$

以及：

$$ b_i = a_i' b_i' c_i + a_i' b_i c_i' = a_i' (b_i \oplus c_i) $$

最后结果是 $b$，因为 $b$ 的二进制位上为 $1$ 时表示这个数字出现了 $1$ 次。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 是数组的长度。

class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    a = b = 0
    for c in nums:
      aa = (~a & b & c) | (a & ~b & ~c)
      bb = ~a & (b ^ c)
      a, b = aa, bb
    return b

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0, b = 0;
    for (int c : nums) {
      int aa = (~a & b & c) | (a & ~b & ~c);
      int bb = ~a & (b ^ c);
      a = aa;
      b = bb;
    }
    return b;
  }
}

class Solution {
public:
  int singleNumber(vector<int>& nums) {
    int a = 0, b = 0;
    for (int c : nums) {
      int aa = (~a & b & c) | (a & ~b & ~c);
      int bb = ~a & (b ^ c);
      a = aa;
      b = bb;
    }
    return b;
  }
};

func singleNumber(nums []int) int {
  a, b := 0, 0
  for _, c := range nums {
    aa := (^a & b & c) | (a & ^b & ^c)
    bb := ^a & (b ^ c)
    a, b = aa, bb
  }
  return b
}

function singleNumber(nums: number[]): number {
  let a = 0;
  let b = 0;
  for (const c of nums) {
    const aa = (~a & b & c) | (a & ~b & ~c);
    const bb = ~a & (b ^ c);
    a = aa;
    b = bb;
  }
  return b;
}

impl Solution {
  pub fn single_number(nums: Vec<i32>) -> i32 {
    let mut a = 0;
    let mut b = 0;

    for c in nums {
      let aa = (!a & b & c) | (a & !b & !c);
      let bb = !a & (b ^ c);
      a = aa;
      b = bb;
    }

    return b;
  }
}