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?

给一串数组，其中数字都是成对出现的，只有两个数字是单独的。

首先，对数组中所有数字以此做异或运算，这样，得到的结果为2个单独数字异或运算的结果。

其次，由于两个数字不相同，所以必至少有一位为1 。

再次，选择某一位为1的，将原数字以此为标准分成两个数组，这样两个单独的数字就会分到两个数组中，而其他相同成对出现的数字也不会分开

最后，两个分开的数组以此对所有元素做异或，最后得到的两个值就是原数组中两个单独出现的值。

想法：

public class Solution {
    public int[] SingleNumber(int[] nums) {
        int result = 0;
        for(int i = 0; i < nums.Count(); i++)
        {
            result ^= nums[i];
        }
        int findOne = 1;
        while((result ^ findOne) != 0)
        {
            findOne = findOne << 1;
        }

        int result1 = 0;
        int result2 = 0;
        for(int i = 0; i < nums.Count(); i++)
        {
            if ((findOne & nums[i]) == 0)
            {
                result1 ^= nums[i];
            }
            else
            {
                result2 ^= nums[i];
            }
        }
        
        int[] returnResult = {result1, result2};
        return returnResult;
    }
}

这样会报超时错误。自己在编译器里使用时可以找出结果的。

 按时间来看，舍掉找findOne从后往前第一个为1的位置的循环，时间复杂度大致为  o(2n)

尚未提交成功

260_Single Number III

原文：http://www.cnblogs.com/Anthony-Wang/p/5048762.html