2/19 的 Daily 是 Eazy 題： 268. Missing Number by Math, Graph Theory and Bit Manipulation

目錄

題目分析

題目

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

分析

找出在 0~n 之中缺少的那個數。問題本身相當簡單，不過要達成附加題的條件 S = O(1)，發現了許多有趣的作法。

解題思路

Counting (Hashmap)

最直覺的作法肯定是counting了。

比如說利用一個陣列來記錄每個數有沒有出現過

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = [True]*(len(nums)+1)
        for i in nums:
            missing[i] = False
        for i, appear in enumerate(missing):
            if appear: return i

或者使用hashmap達到一樣的效果：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        appeared = set(nums)
        return [i for i in range(len(nums)+1) if i not in appeared][0]

不過這種作法，因為需要建立一個記錄用的array(list)或hashmap(set)，空間複雜度為S = O(n)，並無法達到追加題目要求的S = O(1)。

Graph(Linked List)

建立記錄用的表需要消耗O(n)空間，那假如我們直接利用nums本身，透過修改其值來記錄，就不需要額外的空間了！

主要的思路是這樣的：

nums中出現i，就把nums[i]改為-1。最後沒有變成-1的位置，其index就是沒出現過的那個數。

以例題的Ex1為例：

nums = [3,0,1]

  1. 在nums裡面加入一個在[-1,n)區間以外的值，讓陣列的長度為n+1，才能紀錄 0 ~ n

    nums = [3,0,1,3]

  2. 遍歷nums[0:3]，也就是原本的前三格

    1. 第0格的數字是3，因此查看nums[3]，記住其數值為3，並將nums[3]改為-1，紀錄3出現過了

      nums = [3,0,1,-1]

      下一個要記錄的數：3

      查看nums[3]，發現其值已經是-1了，代表3已經出現過。

    2. 繼續遍歷nums，來到第1格，數字是0

      因此檢查nums[0]，記住其值為3，並將nums[0]改成-1，紀錄0出現過了

      nums = [-1,0,1,-1]

      下一個要記錄的數：3

      查看nums[3]，發現其值已經是-1了，代表3已經出現過。

    3. 繼續遍歷nums，來到第2格，數字是1

      因此檢查nums[1]，記住其值為0，並將nums[1]改成-1，紀錄1出現過了

      nums = [-1,-1,1,-1]

      查看nums[0]，發現其值已經是-1了，代表不需要繼續檢查下去。

  3. 結束檢查，此時的nums中，只剩下一個位置不是1：nums[2]

    因此，原本的nums中缺少的數就是2。

範例程式碼：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.append(len(nums))
        for n in nums[:len(nums)-1]:
            i = n
            while i!=-1:
                j = nums[i]
                nums[i] = -1
                i = j
        return [i for i, n in enumerate(nums) if n!=-1][0]

由於這個作法過程中的紀錄都靠直接修改nums的值來完成，所以不需要額外的空間，符合追加題所要求的 S = O(1)

Math

由於題目的nums裡面含有0~n中的所有數、只缺少其中的一個數，所以我們可以利用等差級數和的公式直接得知少哪一個數。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return len(nums)*(len(nums)+1)//2 - sum(nums)

因為需要求sum(nums)，時間複雜度仍為T = O(n)

直接代公式不需要紀錄用的陣列，因此空間複雜度符合追加題所要求的S = O(1)

Bit XOR Sum (Bit Manipulation)

雖然有點拿牛刀殺雞的感覺，不過以下利用bit xor操作的特性的作法是本文解法中我最喜歡的。因為很酷(X)

引理：

  1. 　a xor a == 0

  2. 　a xor 0 == a

  3. 　XOR運算滿足結合律 (順序互換答案相同)，即 a xor b xor c == a xor c xor b

因此，若把0~n中的所有數，和nums中的所有數全部連著作 xor 運算

在nums中有出現的數都會成雙成對，然後經過xor變成0。因此最終剩下來的答案就是nums中未出現的數。

例如：

nums = [3,0,1] , n = len(nums) = 3

(3 xor 0 xor 1) xor (0 xor 1 xor 2 xor 3) 
= (0 xor 0) xor (1 xor 1) xor 2 xor (3 xor 3)
=  0        xor  0        xor 2 xor  0
= 2

範例程式碼：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return (reduce(lambda p, i: p^i^nums[i],(i for i in range(len(nums))),len(nums)))

時間複雜度仍為T = O(n)

由於只需要一個變數來持續記錄每次xor運算之後的結果，空間複雜度符合追加題所要求的S = O(1)。

結語

Leetcode 的 Easy 和 Medium 題有時候會出現這種Follow up(追加題)，往往都能從中獲得有趣的知識！

感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！