题目描述：

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:

The order of the result is not important. So in the above example, [5, 3] is also correct.

Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

题目大意：

给定一个整数数组，其中除两个数字只出现一次外，其余数字均出现两次。找出这两个只出现一次的数字。

例如：

给定 nums = [1, 2, 1, 3, 2, 5]，返回 [3, 5]

注意：

结果的顺序不重要。因此在上例中，[5, 3]也是正确的。

你的算法应该满足线性时间复杂度。你可以只使用常数空间复杂度完成题目吗？

解题思路：

参考LeetCode Discuss

链接地址：https://leetcode.com/discuss/52351/c-o-n-time-o-1-space-9-line-solution-with-detail-explanation

首先计算nums数组中所有数字的异或，记为xor

令lowbit = xor & -xor，lowbit的含义为xor从低位向高位，第一个非0位所对应的数字

例如假设xor = 6（二进制：0110），则-xor为（二进制：1010，-6的补码，two's complement）

则lowbit = 2（二进制：0010）

根据异或运算的性质，“同0异1”

记只出现一次的两个数字分别为a与b

可知a & lowbit与b & lowbit的结果一定不同

通过这种方式，即可将a与b拆分开来

Python代码：

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def singleNumber(self, nums):
        xor = reduce(lambda x, y : x ^ y, nums)
        lowbit = xor & -xor
        a = b = 0
        for num in nums:
            if num & lowbit:
                a ^= num
            else:
                b ^= num
        return [a, b]

上述代码可以精简为三行：

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def singleNumber(self, nums):
        xor = reduce(operator.xor, nums)
        ans = reduce(operator.xor, filter(lambda x : x & xor & -xor, nums))
        return [ans, ans ^ xor]

或者将filter + lambda换成generator，效率更高

参考：https://leetcode.com/discuss/52387/3-line-python-code

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def singleNumber(self, nums):
        xor = reduce(operator.xor, nums)
        ans = reduce(operator.xor, (x for x in nums if x & xor & -xor))
        return [ans, ans ^ xor]

 

本文链接：http://bookshadow.com/weblog/2015/08/17/leetcode-single-number-iii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码