leetcode260.Single Number III

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

假设一个整数数组中，除了两个数字以外，所有的数字都出现了两遍。要求我们找到这两个数字。

可以先参考Single Number I 和 Single Number II。

思路与代码

这里需要了解两个位运算的重要知识：

  1. a^b^b = a 即b^b=0
  2. a&(-a)能够获得a的二进制形式的最右侧的1的位置。

举例解释一下第二个位运算：
一个数的负数是通过计算其正数的补码获得的。比如5的八位二进制为00000101，那么其反码为11111010，再在反码上加一得到其补码11111011也就是-5的二进制形式。
那么我们可以知道，一个数与其反码的与运算，得出的结果一定为0。而反码加一则代表着将原数的最后一位1在反码上也置为1。从而获得二进制最右侧1的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] singleNumber(int[] nums) {
   int diff = 0;
    for(int num : nums){
        diff ^= num;
    }
    
    diff &= -diff;
    
    int[] result = {0, 0};
    for(int num : nums){
        if((num & diff) == 0){
            result[0] ^= num;
        }else{
            result[1] ^= num;
        }
    }
    return result; 
}