260. Single Number III

[qianlei90]

260. Single Number III

Tags: 印象笔记

[toc]

---

Question

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?

Solution

1. 如果只有1个数字出现1次，其他数字都出现2次，那所有数字异或后的值就是这个数字。现在有2个数字出现1次，那所有数字异或之后就是这两个数字的异或值。
2. 假设这个值的第n位为1，对应的数字是x(x=2^n-1)，可利用x将所有的数字分成两组，一组是与x异或后第n位为0的，一组是不为0的。为了方便，下面的代码取n为从右到左第一个为1的那一位。
3. 两个数字分别在这两组数字中，所以按照1中的结论，对每组数字进行异或，就能得到那个数字。

Show me the code

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        from operator import xor

        all_xor = reduce(xor, nums)     # 这两个数字的异或值
        last_bit = all_xor & -all_xor   # 取到最右边的那个1，具体百度"x & -x"

        # last_bit只有1位为1，其他位都为0
        list1 = [x for x in nums if not (x & last_bit)]
        list2 = [x for x in nums if (x & last_bit)]

        return [reduce(xor, list1), reduce(xor, list2)]

- 完 -