LeetCode:260. Single Number III

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

:

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

   [5, 3]

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

Credits:

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

题意：给定数组中有且只有两个数只出现1次，其他数全部出现2次，找出这两个数。

分析：找出出现1次的数，首先想到异或操作，然而存在两个只出现1次的数，那就要想办法把这两个数分开。因为这两个数不同（如果相同，那么都出现两次），说明两个数的二进制表示中至少有一位是不相同，如果根据该位将数组分成两部分，然后分别异或，那么两组的异或结果便是这两个数。那么如何找到二进制不同的位呢？可以先对整个数组异或，结果必然不是0，只要找到这个异或结果的某一非0位，即是两个数不同的位。

代码如下：

class Solution {
    public int[] singleNumber(int[] nums) {
        int n=;
        for(int i=;i<nums.length;i++){
            n=n^nums[i];
        }
        int m=;
        while((n&m)==) m=m<<;
        n=;
        int n2=;
        for(int i=;i<nums.length;i++){
            if((nums[i]&m)==){
                n=n^nums[i];
            }
            else
                n2=n2^nums[i];
        }
        int[] result=new int[];
        result[]=n;
        result[]=n2;
        return result;
    }
}