leetcode_260

发表于   |   分类于

Single Number III

题目戳这

题意

给你一个数组，里面有且仅有两个数字出现一次，其他数字都出现两次。现在让你用O(n)的时间效率和O(1)的空间效率找出这两个只出现了一次的数字。

解法

我感觉做了这么多题，这道题目真的让我神清气爽，想法真的只能用一个字来形容，就是妙！
好了废话不多说，照搬下大牛的思路。

如果有两个数字不一样，那么说明它们的二进制表示肯定是至少有一位不同的。那么它俩亦或的结果的二进制表示中，1代表的就是它俩不同的位(亦或嘛，不同为1)。那么我们先找到最右边的那个1位，怎么找？记得树状数组那个神奇的lowbit公式吗？那就是找最低位的1，所以如果一个数为x,那么它的最低位的1就是x&(-x)。

因为这道题目中只有两个数字出现过一次，其他数字都是出现两次，那么按照亦或的定义，我们把数组中全部的数字亦或起来，得到的就是那两个只出现一次的数字的亦或值。接着就按照上述的找最右边的二进制位为1所代表的值，其他位都为0，假设这个值就为ssum。

接下去就很精妙了，我们开始遍历数组，假设数组数字为x，那么这个数组中的值就可以被分为两个集合，分别为 (x&ssum > 0) 以及 (x&ssum == 0)的。为什么可以这么分？首先我们先看除了那两个数字以外其它的数字，我们发现，两个相同的数字肯定是出现在同一个集合中的，这不用说。对于那两个数字来说，一个肯定是在>0 的集合中，一个肯定是在=0的集合中，因为刚才我们说明了，ssum代表的是两个数字亦或值最右边的那个1所代表的值，这个1就是那两个数字的至少不同的那一位，所以肯定一个为0，一个为>0！

这就将数字分成了两个集合，假如原数组是[1, 2, 1, 3, 2, 5],那么这两个集合分别为:

> 0: 2，2，3
= 0：1，1，5

得到这两个集合后咋办？亦或啊！把这两个单独出现的数字分开以后一亦或，就可以得到答案了。。
太神！

代码

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
28
29
30
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        # python三行
        # xor = reduce(lambda x,y:x^y, nums)
        # ssum = reduce(lambda x,y:x^y, (x for x in nums if x&xor&-xor))
        # return [ssum, ssum^xor]
        
        
        ssum = 0
        for x in nums:
            ssum ^= x
        
        ssum = ssum & -ssum
        
        num1 = 0
        num2 = 0
        
        for x in nums:
            if x & ssum > 0:
                num1 ^= x
            else:
                num2 ^= x
            
        
        return [num1, num2]