137. 只出现一次的数字 II
题目描述
输入一个整数数组 nums。其中有一个值只出现一次，其余每个值都恰好出现三次。
返回那个只出现一次的值。
算法需要线性时间，并且只使用常数级的额外空间。
示例 1
输入：nums = [2,2,3,2] 输出：3
解释：2 出现三次，3 只出现一次。
示例 2
输入：nums = [0,1,0,1,0,1,99] 输出：99
解释：0 和 1 各出现三次，只有 99 出现一次。
数据范围
1 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1- 除一个值只出现一次外，其余值都恰好出现三次。
解题思路：逐位计数
按二进制位分别统计。对第 k 位，数一数所有数在这一位上 1 的个数 cnt。出现三次的数在每一位上贡献 0 或 3，所以 cnt % 3 就是那个单独数在第 k 位的值。把 32 位逐一拼回去即可；第 31 位是符号位，Python 中需把 ≥ 2^31 的结果减去 2^32 还原为负数。
为什么正确
对每一位 k：cnt_k = 3·(出现三次的数中第 k 位为 1 的个数) + (单独数的第 k 位)，因此 cnt_k mod 3 恰为单独数的第 k 位。
复杂度分析
时间 O(32·n)；空间 O(1)。
易错点
用异或只能处理“出现两次”的情形，这里行不通；Python 的整数没有 32 位上限，第 31 位置 1 后得到的是一个很大的正数，必须减去 2^32 才是正确的负数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for k in range(32):
cnt = 0
for x in nums:
cnt += (x >> k) & 1
if cnt % 3:
ans |= 1 << k
if ans >= 2 ** 31:
ans -= 2 ** 32
return ansclass Solution {
public int singleNumber(int[] nums) {
long ans = 0;
for (int k = 0; k < 32; k++) {
int cnt = 0;
for (int x : nums) {
cnt += (x >> k) & 1;
}
if (cnt % 3 != 0) {
ans |= 1L << k;
}
}
if (ans >= (1L << 31)) {
ans -= 1L << 32;
}
return (int) ans;
}
}class Solution {
public:
int singleNumber(vector<int>& nums) {
long long ans = 0;
for (int k = 0; k < 32; k++) {
int cnt = 0;
for (int x : nums) {
cnt += (x >> k) & 1;
}
if (cnt % 3) {
ans |= 1LL << k;
}
}
if (ans >= (1LL << 31)) {
ans -= 1LL << 32;
}
return (int)ans;
}
};func singleNumber(nums []int) int {
ans := 0
for k := 0; k < 32; k++ {
cnt := 0
for _, x := range nums {
cnt += (x >> k) & 1
}
if cnt%3 != 0 {
ans |= 1 << k
}
}
if ans >= 1<<31 {
ans -= 1 << 32
}
return ans
}var singleNumber = function(nums) {
let ans = 0;
for (let k = 0; k < 32; k++) {
let cnt = 0;
for (const x of nums) {
cnt += (x >> k) & 1;
}
if (cnt % 3) {
ans += 2 ** k;
}
}
if (ans >= 2 ** 31) {
ans -= 2 ** 32;
}
return ans;
};function singleNumber(nums: number[]): number {
let ans = 0;
for (let k = 0; k < 32; k++) {
let cnt = 0;
for (const x of nums) {
cnt += (x >> k) & 1;
}
if (cnt % 3) {
ans += 2 ** k;
}
}
if (ans >= 2 ** 31) {
ans -= 2 ** 32;
}
return ans;
}其他解法
哈希计数最直观但要 O(n) 空间；逐位计数和状态机都是 O(1) 空间，状态机把 32 轮扫描压成一轮。
解法 2：数字电路状态机 时间 O(n)，空间 O(1)
用 ones 和 twos 两个整数的对应位表示该位出现次数模 3 的状态：00、01、10 循环。每读入一个 x，先用 ones = (ones ^ x) & ~twos 更新低位，再用 twos = (twos ^ x) & ~ones 更新高位。出现三次的位回到 00，最后 ones 就是答案。
只遍历一次，并且所有 32 位同时并行处理。更新公式需要推导真值表，不易想到。
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones = twos = 0
for x in nums:
ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones
return onesclass Solution {
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for (int x : nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}
}class Solution {
public:
int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
for (int x : nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}
};func singleNumber(nums []int) int {
ones, twos := 0, 0
for _, x := range nums {
ones = (ones ^ x) &^ twos
twos = (twos ^ x) &^ ones
}
return ones
}var singleNumber = function(nums) {
let ones = 0, twos = 0;
for (const x of nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
};function singleNumber(nums: number[]): number {
let ones = 0, twos = 0;
for (const x of nums) {
ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;
}
return ones;
}解法 3：哈希计数 时间 O(n)，空间 O(n)
用哈希表统计每个数出现的次数。再遍历哈希表，返回次数为 1 的数。
写法最简单，也适用于出现次数任意的变体。需要 O(n) 额外空间。
from collections import Counter
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
cnt = Counter(nums)
for x, c in cnt.items():
if c == 1:
return x
return 0class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
if (e.getValue() == 1) return e.getKey();
}
return 0;
}
}class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
for (auto& [x, c] : cnt) {
if (c == 1) return x;
}
return 0;
}
};func singleNumber(nums []int) int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
for x, c := range cnt {
if c == 1 {
return x
}
}
return 0
}var singleNumber = function(nums) {
const cnt = new Map();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
for (const [x, c] of cnt) {
if (c === 1) return x;
}
return 0;
};function singleNumber(nums: number[]): number {
const cnt = new Map<number, number>();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
for (const [x, c] of cnt) {
if (c === 1) return x;
}
return 0;
}