GuilinDev

Lc0260

05 August 2008

260 - Single Number III

题目

Given an array of numbers 

1

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.

Example:

1
2

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

  1. The order of the result is not important. So in the above example, 
    1

    [5, 3]
    is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

分析

这道题考察的是位操作，需要比较清楚的二进制编码，反码，补码的知识；首先第一次遍历将array中所有的元素进行XOR操作，得到的结果diff是需要找出的两个只出现一次的元素相互之间的XOR操作，这时候将diff和其负数作&与操作，得到新的diff包含了所有1的位置，然后作第二次遍历，同样，出现两次的元素自我抵消掉；剩下的两个单独数字之中，其中有一个必然与diff作与&操作为0，记录，另一个不为零，记录。

代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int[] singleNumber(int[] nums) {
        
        int diff = 0;
        
        // 1.找出只出现一次的两个数的二进制
        for (int num : nums) {
            diff ^= num;
        }
        
        // 2.与自己的补码与操作，得到最后一个bit，0或者1（自己与自己负数-补码，只是最后一位相同，别的31位都不同）
        diff &= -diff;
        
        int[] result = new int[2];
        
        // 3.分离两个数
        for (int num : nums) {
            if ((diff & num) == 0) {
                result[0] ^= num; //用xor是因为要把diff &= -diff这步得到的bit相同的num彼此消掉（别的num出现两次）
            } else {
                result[1] ^= num; //用xor是因为要把diff &= -diff这步得到的bit不同的num彼此消掉（别的num出现两次）
            }
        }
        
        return result;
    }
}
This site is open source. Improve this page.