本文完整拆解 LeetCode 268 Missing Number 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Missing Number 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
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.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?
Python
# time complexity: O(n)
# space complexity: O(1)
from typing import List
class Solution:
def missingNumber(self, nums: List[int]) -> int:
numSet = set(nums)
for i in range(len(numSet) + 1):
if i not in numSet:
return i
nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
print(Solution().missingNumber(nums))
Missing Number 解題思路
0 到 n 共 n+1 個數字少了一個,有兩種漂亮解法:一是用高斯求和公式算出「應有總和」再減去實際總和;二是用 XOR——把 0 到 n 與陣列中所有數字全部 XOR 起來,成對的會互相抵消,剩下的就是缺失值。XOR 版不會溢位,更安全。
Missing Number 演算法步驟
- 初始化 result = n(補上索引走不到的那個數)。
- 走訪陣列,索引為 i、值為 nums[i]。
- 令 result = result XOR i XOR nums[i]。
- 走完後 result 就是缺失的數字。
Missing Number 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(n) |
| 空間複雜度 | O(1) |
單次線性掃描,每步兩次 XOR,時間為 O(n)。只用一個變數,空間 O(1)。相較求和法,XOR 完全沒有溢位風險。
Missing Number 的邊界情況與常見錯誤
- 缺失的可能是 0 或 n 本身,兩端都要能正確處理。
- 求和法在 n 很大時可能溢位,XOR 法沒有這個問題。
- 陣列保證沒有重複且都在 0 到 n 範圍內,否則兩種解法都會失效。
- 排序後找斷點也可行,但多花 O(n log n)。
Missing Number 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| 排序後掃描找斷點 | O(n log n) | O(1) | 正確但較慢 |
| 用集合記錄出現過的數 | O(n) | O(n) | 多花一份空間 |
| XOR 抵消 | O(n) | O(1) | 本文採用 |
