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

题目

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

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

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

示例 1:

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

示例 2:

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

提示：

• nums.length <= 30000

题解1

思路

• 将数组排序，若$nums[i]-nums[i-1]\ne 1$则说明$nums[i]-1$不在数组中
• 同时将消失的数字在数组首和数组尾两种情况单独考虑

代码

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        if not nums: return [1,2]
        elif len(nums) == 1:
            if nums[0] == 1: return [2,3]
            elif nums[0] == 2: return [1,3]
            elif nums[0] == 3: return [1,2]
            else: assert False
        nums.sort()
        ret = []
        if nums[0] > 2: return [1,2]
        elif nums[0] == 2: ret.append(1)
        i = 1
        while i < len(nums):
            if nums[i] - nums[i-1] > 1:
                ret.append(nums[i] - 1)
            i+=1
        if len(ret) == 0:
            ret.append(nums[-1] + 1)
            ret.append(nums[-1] + 2)
        elif len(ret) == 1:
            ret.append(nums[-1] + 1)
        return ret

复杂度

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(\log n)$

题解2

思路

• 数组的长度为$n$则说明$[1,n+2]$区间内，不曾出现过的数则说明消失了

代码

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        visited = [False] * (len(nums)+2)
        for n in nums:
            visited[n-1] = True
        ret = []
        for i in range(len(visited)):
            if not visited[i]: ret.append(i+1)
        return ret

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题解3

思路

• 假设数组消失的数为$x_1,x_2$，则$x_1+x_2=\sum num-\sum (range(1,n+2))$
• 若输入为哈希表，则可以通过$x_1\notin nums\wedge x_2\notin nums$来判断 可惜不是╮(╯▽╰)╭

代码

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        s = set(nums)
        n = len(s)
        currentSum = sum(s)
        expectSum = (n+2)*(n+3)//2
        diff = expectSum - currentSum
        for i in range(1, n+3):
            if i not in s and (diff - i) not in s and (diff-i)<n + 3: return [i, diff-i]

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题解4

思路

• 继题解3，考虑构造线性无关方程组，考虑：
  { a = x 1 + x 2 = ( n + 2 ) ( n + 3 ) 2 − ∑ ( n u m s ) b = x 1 2 + x 2 2 = ( n + 2 ) ( n + 3 ) ( 2 n + 5 ) 6 − ∑ n   ∈ n u m s ( n 2 ) \left\{

  a=x1+x2=(n+2)(n+3)2−∑(nums)b=x12+x22=(n+2)(n+3)(2n+5)6−∑n ∈nums(n2)" role="presentation">a=x1+x2=(n+2)(n+3)2−∑(nums)b=x21+x22=(n+2)(n+3)(2n+5)6−∑n ∈nums(n2)$$\begin{array}{rl}& a=x_1+x_2=\frac{(n+2)(n+3)}{2}-\sum (nums)\\ & b=x_1^2+x_2^2=\frac{(n+2)(n+3)(2n+5)}{6}-\sum _{n\in nums}(n^2)\end{array}$$
  \right. ⎩ ⎨ ⎧​​a=x1​+x2​=2(n+2)(n+3)​−∑(nums)b=x12​+x22​=6(n+2)(n+3)(2n+5)​−n ∈nums∑​(n2)​

• 可以求解
  δ = 2 b − a 2 { x 1 = a + δ 2 x 1 = a − δ 2 \delta = \sqrt{2b-a^2}\\ \left\{

  x1=a+δ2x1=a−δ2" role="presentation">x1=a+δ2x1=a−δ2$$\begin{array}{rl}& x_1=\frac{a+\delta }{2}\\ & x_1=\frac{a-\delta }{2}\end{array}$$
  \right. δ=2b−a2 ​⎩ ⎨ ⎧​​x1​=2a+δ​x1​=2a−δ​​

代码

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums)
        currentSum = sum(nums)
        currentSquareSum = sum(map(lambda x: x*x, nums))
        expectSum = (n+2)*(n+3)//2
        expectSquareSum = (n+2)*(n+3)*(2*n+5)//6
        a = expectSum - currentSum
        b = expectSquareSum - currentSquareSum
        delta = math.sqrt(2 * b - a * a)
        return [int((a + delta)//2), int((a-delta)//2)]

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

题解5

思路

• 对所有数和$[1,n+2]$中的所有数位运算，最后得到的结果为$x_1\oplus x_2$
• 因为python中负数使用补码表示，所以可以使用$xorsum\oplus -xorsum$作为掩码进行分类
• 分组后再通过掩码计算分别求出两个不同的数

代码

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        xorSum = 0
        for n in nums:
            xorSum ^= n
        for n in range(1, len(nums) + 3):
            xorSum ^= n
        mask = xorSum & (-xorSum)
        n1, n2 = 0,0
        for n in nums:
            if n&mask:
                n1 ^= n
            else:
                n2 ^= n
        for n in range(1, len(nums) + 3):
            if n&mask:
                n1 ^= n
            else:
                n2 ^= n
        return [n1,n2]

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$