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?

思路：很久沒解題了，發(fā)現(xiàn)一點(diǎn)思路也沒有了。

一，python的set是一個(gè)無(wú)序不重復(fù)元素集，基本功能包括關(guān)系測(cè)試和消除重復(fù)元素. 集合對(duì)象還支持并、交、差、對(duì)稱差等。所以這里可以使用set的這個(gè)功能。使用兩個(gè)set分別放nums立面的數(shù)據(jù)，一個(gè)set里面已經(jīng)有的，就放入另外一個(gè)，二者差值就是我們要求的。

二， 使用亦或，如果對(duì)所有nums里面的數(shù)都使用異或，最后的結(jié)果就是我們要求的數(shù)異或的結(jié)果，因?yàn)槠渌貜?fù)的值異或的結(jié)果變成0了。然后查看這兩個(gè)數(shù)異或的結(jié)果，如果一些字節(jié)異或的結(jié)果為1，則表明這兩個(gè)數(shù)在那個(gè)位置不同。

然后把所有數(shù)字分成兩組，一組是在對(duì)應(yīng)位置為1的，另一組在對(duì)應(yīng)位置不為1。兩個(gè)不同的數(shù)字就是我們要找的。

技巧： diff &= -diff

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        one = set()
        double = set()
        for n in nums:
            if n not in one:
                one.add(n)
            else:
                double.add(n)
        print one
        print double
        return list(one - double)

    def singleNumber2(self, nums):
        diff = 0
        for n in nums:
            diff ^= n
        #Get its last set bit
        diff &= -diff

        res = [0, 0]
        for n in nums:
            if(n&diff==0):
                res[0] ^= n
            else:
                res[1]^=n

        return res

if __name__ == '__main__':
    sol = Solution()
    nums = [1, 2, 1, 3, 2, 5]
    print sol.singleNumber(nums)
    print sol.singleNumber2(nums)