面试题 17.19. 消失的两个数字

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示：

• nums.length <= 30000

Python 解答：
1.

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        length = len(nums)
        nums.extend([3, 3])
        for i in range(length):
            if nums[i] > 0:
                nums[nums[i]-1] *= -1
            else:
                nums[-nums[i]-1] *= -1
        return [i+1 for i in range(length+2) if nums[i] > 0]

2.异或

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        temp1, temp2 = 0, 0
        for item in nums:
            temp1 ^= item
        for item in range(1, len(nums)+3):
            temp2 ^= item
        temp = temp1^temp2
        j = 0
        while j < 32:
            if temp & 1:
                break
            temp >>= 1
            j += 1
        one, two = 0, 0
        for item in nums:
            if (item>>j) & 1:
                one ^= item
            else:
                two ^= item
        for i in range(1, len(nums)+3):
            if (i>>j) & 1:
                one ^= i 
            else:
                two ^= i
        return [one, two]