LeetCode 260. Single Number III

2016-05-28  本文已影响785人  无关风月只关情

原题链接:https://leetcode.com/problems/single-number-iii/

给出一个数组,其中有两个元素仅有一个,其它均有两个,要求找出仅有一个的两个数字。

首先最直观的解法,维护一个 set,遍历原数组,没有的加进去,有的移出,最后剩下的就是就是只有一个的了。
该方法的时间复杂度是 O(N),空间复杂度也是 O(N)。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = set()
        for n in nums:
            if n in result:
                result.remove(n)
            else:
                result.add(n)
        return list(result)

题目说有O(1)空间复杂度的姐,可以想到的思路是 set 的添加和删除改成用一个常数来存储,用位操作来保存。

想了很久没想出来,最后去看了下讨论,终于理解了。
主要用到的是异或的一些特性。

以前有个经典例子,使用异或可以不借助中间变量交换两个数字:

In [203]: a, b = 1, 2
In [204]: a = a ^ b
In [205]: b = a ^ b
In [206]: a = a ^ b
In [207]: print a, b
2 1

一些其他特性:

0 ^ n = n
n ^ n = 0

题中仅有两个值是唯一的,其它都恰好只有两个。
因此全部进行异或的结果等于只异或两个答案的结果:

假定:

l = [a, b, c1, c2, d1, d2, ......, z1, z2]

中,a,b 是唯一的两个数,其它字母相同的是同样的数。
那么:

c1 ^ c2 = 0
...
z1 ^ z2 = 0

a ^ b ^ c1 ^ c2 ^ ... ^ z1 ^ z2 = a ^ b ^ (c1 ^ c2) ^ ... ^ (z1 ^ z2) = a ^ b ^ 0 ^ ... ^ 0 = a ^ b

因为 a 和 b 是不同的,即 a ^ b != 0,因此他们至少有一位是不同的,如对于 3 和 5 而言,

   011  -> 3
^ 101  -> 5   
----------
   110  -> 6

6 的右数第二、三位均为 1,即 3 和 5 的右数第二、三位是不同的,因此我们可以用这一位来区分 3 和 5。如取第二位,则为 10,值为2。

2 & 3 = 2
2 & 5 = 0

用回 a 和 b 表示即为:若 s = a ^ b,找出 s 从右到左第一个不为 0 的位:

mask = 1
while (s & mask == 0):
     mask = mask << 1

然后再次遍历数组,使用条件 num & mask == 0 将数字分为两组,分别取异或 s ,则可以得到 a 和 b。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        bit_num = 0
        for num in nums:
            bit_num ^= num
        mask = 1
        a = b = bit_num
        while (bit_num & mask == 0):
            mask = mask << 1
        for num in nums:
            if (num & mask):
                a ^= num
            else:
                b ^= num
        return [a, b]
上一篇下一篇

猜你喜欢

热点阅读