Leetcode 260. 只出现一次的数字III

(Updated: )
(1 min to read)

题意

有一个数组nums，其中有两个数字只出现了1次，其余数字都出现了恰好2次，问只出现1次的那两个数字。

做法

除了异或外想不到能再获取什么有用的信息，最后看了眼题解才会🤡。。

首先把所有数异或起来可以知道这两个数字x和y的异或值。

下面就是关键了，由于x != y，x ^ y一定有某一位是1，且x和y在该位上一个是1，一个是0。于是把数组按照该位的取值分成两份，就退化为问题《只出现一次的数字I》了，分别异或即可。

计算某一位可以用x & (-x)得到最低位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
        let mut xor = 0;
        for num in nums.iter() {
            xor ^= num;
        }
        let low_bit = xor & (-xor);
        let mut x = 0;
        let mut y = 0;
        for num in nums {
            if num & low_bit != 0 {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        vec![x, y]
    }
}