跳转至

137. 只出现一次的数字 II

题目描述

给你一个整数数组 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 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

解法

方法一：位运算

思考

其余数出现三次、一个出现一次，异或不再直接可用，因为 \(x\oplus x\oplus x=x\)。进阶仍要常数空间。按位统计 \(1\) 的个数再模 \(3\)，出现三次的位被清掉，余数即答案对应位。符号位单独处理以免溢出。

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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)
}

1
2
3
4
5
6
7
8
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;
}

1
2
3
4
5
6
7
8
function singleNumber(nums) {
    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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]
    }
}

方法二：数字电路

思考

方法一对每个位扫描整数组。用两个整数 \(a,b\) 按位表示「该位出现次数模 \(3\)」，读入下一个数时按真值表更新，一遍扫描完成同样的模 \(3\) 计数。

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

一个整数的每个二进制位是 \(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\) 是数组的长度。

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

1
2
3
4
5
6
7
8
9
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function singleNumber(nums) {
    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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

方法三：哈希表 + 数学

思考

不限制额外空间时，唯一数等于 \((3\sum_{\mathrm{unique}}-\sum_{\mathrm{all}})/2\)。集合去重后做两次求和即可，思路直接，但空间是 \(O(n)\)。

1
2
3
4
5
function singleNumber(nums: number[]): number {
    const sumOfUnique = [...new Set(nums)].reduce((a, b) => a + b, 0);
    const sum = nums.reduce((a, b) => a + b, 0);
    return (sumOfUnique * 3 - sum) / 2;
}

1
2
3
4
5
function singleNumber(nums) {
    const sumOfUnique = [...new Set(nums)].reduce((a, b) => a + b, 0);
    const sum = nums.reduce((a, b) => a + b, 0);
    return (sumOfUnique * 3 - sum) / 2;
}

方法四：位运算

思考

方法二的状态机可以收成两个掩码：用 \(\textit{ans}\) 与 \(\textit{acc}\) 分别记下「出现一次」「出现两次」的位，按 \(x\) 更新后互斥，最后 \(\textit{ans}\) 即只出现一次的数。实现更短。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function singleNumber(nums: number[]): number {
    let [ans, acc] = [0, 0];

    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }

    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function singleNumber(nums) {
    let [ans, acc] = [0, 0];

    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }

    return ans;
}

评论