LC.P136[只出现一次的数字III]

方法一：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] singleNumber(int[] nums) {
        int xs = 0;
        for (int x : nums) {
            xs ^= x;
        }
        int lowbit = xs & -xs;
        int a = 0;
        for (int x : nums) {
            if ((x & lowbit) != 0) {
                a ^= x;
            }
        }
        int b = xs ^ a;
        return new int[] {a, b};
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$