一魚多吃 用XOR性質來解 失蹤的數字Missing Number Leetcode #268

這題題目在這裡:

題目會給定一個陣列，長度為n，裡面的數字都是獨一無二，落在0~n的範圍。

要求我們找出那個不見的數字 Missing Number

註:
(n+1)個數字，無法同時放入n個不同的格子，必定有一個數字不見了。

測試範例:

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 <= 104
• 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?

演算法:

除了傳統的集合檢查法之外，我們還可以用化簡的技巧，把這題映射到另一個問題Single Number，就可以用XOR Self-inverse的特性來找出Missing Number。

我們把 array index 一起加進來考慮，可以得到如下的示意圖

再次回顧這個重要的性質(類似鴿籠原理的衍伸):

0~n 總共(n+1)個數字，無法同時放入n個不同的格子，必定有一個數字不見了。

令 missing_finder 初始值為 n = 陣列長度

接著對index滾動計算XOR，再對陣列本身裡面的數字滾動計算XOR，最後留下來的數字，就是我們的所求 Missing Number。

為什麼? 因為，扣掉 Missing Number之外的數字，其他數字都會成雙成對出現兩次，一次是在index，一次是在陣列本身裡面的數字 或者 missing_finder 的初始值。

例如:

array = [0, 1, 3]

index = [0, 1, 2]

Result 初始值 = n = 陣列長度 = 3

所有數字，除了missing number 2 之外，其他數字0, 1, 3都會成雙成對出現兩次。

程式碼:

class Solution:
　def missingNumber(self, nums: List[int]) -> int:
　　
　　size = len(nums)
　　
　　missing_finder = size
　　
　　for index, number in enumerate(nums):
　　　
　　　# all existed number must exist twice, one in index, the other in number
　　　# only the missing one exist once, so it will remained in missing finder naturally due to XOR property
　　　missing_finder ^= ( index )
　　　missing_finder ^= ( number )
　　　
　　return missing_finder

時間複雜度:

O( n ) 只需要一次線性掃描。

空間複雜度:

O( 1 ) 只需要臨時變數去儲存XOR 滾動計算的結果。

學完這題之後，記得吸收沉澱一下，
回去複習 Single Number 和 Find the difference 這兩題喔，背後用到的都是同樣的觀念，也都用到 XOR 運算子 Self-inverse的成雙成對互相消去的特質。

Reference:

[1] undefined - Missing Number - LeetCode