Leetcode解题-Single Number III

发表于   |   分类于   |  

描述

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?

分析

和Single Number基本设定一致，区别在于这次有两个出现一次的数，设为x和y。这给我们了一点启发，那我们是不是可以套用[Single Number]的解法呢？是可以的，不过我们给所有数取异或后，剩下的值是 $ z = x \oplus y
$，这时候我们要怎么把x和y给分别求出来呢？我们只需要用一个bit位就能够区分出来，任取z的为1的某一位（说明x和y在这一位上不一致），把原数组中这一位是1的数放到一拨，为0的放到一拨，分别取异或，就解出了x和y。

取z的某一位为1的bit位，可以就用LSB，它有一个漂亮的求法n & -n，更多位运算的奇技淫巧看这里：Bit Twiddling Hacks。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        z = reduce(lambda x, y: x ^ y, nums)
        lsb = z & -z
        x, y = 0, 0
        for n in nums:
            if n & lsb:
                x ^= n
            else:
                y ^= n
        return [x, y]

热评文章