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

260.只出现一次的数字 III

题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

方法（位运算）

由于两个相同的数字异或的结果为0，因此将数组中所有元素异或得到的结果res即为两个Single Number异或的结果

我们进行如下考虑：
如果我们将数组中的元素分为两组，每组中只有一个Single Number，那么只要把这两个组的组内元素全部异或，就会分别得到两个Single Number。

但是如何进行分组才能将两个Single Number正确地分到两个组呢？
我们在上面得到了两个Single Number异或得到的结果res。在res中为1的bit位上，两个Single Number的取值肯定不同（如果两个数在这一位上都为1或者都为0，那么异或结果在这一位上必然为0）。我们可以用这一特性来进行分组：

  • 先找到res中值为1的最低bit位
  • 在这一位上为1的元素放到一组，在这一位上为0的元素放到另一组

这样就可以保证两个Single Number被分到两个不同的组，而且同样的元素肯定会被分到同一组。最后组内进行异或，便可分别得到这两个Single Number

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] singleNumber(int[] nums) {
    int res = 0;
    for(int num : nums)
        res ^= num;
    int lowbit = res & (-res);
    int num1 = 0;
    int num2 = 0;
    for(int num : nums){
        if((num & lowbit) == 0)
            num1 ^= num;
        else
            num2 ^= num;
    }
    return new int[]{num1, num2};
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

注：
将一个数与它的相反数进行与操作，可以获得这个数中值为1的最低bit位。

1
int lowbit = res & (-res)

因为在计算机中，-res由res中的各位都取反，再在最低位上加1来得到