一魚多吃 用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.length1 <= n <= 1040 <= nums[i] <= n- All the numbers of
numsare 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:
