260.md

260. Single Number III

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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.

Example:

Input:  [1,2,1,3,2,5]
Output: [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?

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

思路见第136题，在那个基础上面，

如果可以把two number的问题变成两个single number的问题，就可以套用之前第136题的解法了， 也就是说我们可以通过某种方式把数组分为两组，每组只包含那两个special number中的一个。

问题的关键就变成如何分组了。思路也是有点巧妙，考虑到两个special number是不一样的， 而恰好其余的数都是出现两次，所以如果对每个数都做亦或操作， 最后的结果就是那两个special number的亦或，而且至少有一个位是1，那么就可以根据其中一个为1的位将所有的数分为两组，再套用第136题的方法即可。

beats 99.59%

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        xor, a ,b = 0, 0, 0
        for num in nums:
            xor ^= num
            
        mask = 1
        while xor & mask == 0:
            mask = mask << 1
            
        for num in nums:
            if num & mask: # 该bit上为1的数字
                a ^= num   # 第一组
            else:          # 该bit上为0的数字  
                b ^= num   # 第二组
        return [a, b]

参考 Leetcode Single Number 问题总结