Missing Number 解題教學:3 種解法完整比較|LeetCode 268 Best Practice

Missing Number 解題教學示意圖|LeetCode 268

本文完整拆解 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.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?

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 演算法步驟

  1. 初始化 result = n(補上索引走不到的那個數)。
  2. 走訪陣列,索引為 i、值為 nums[i]。
  3. 令 result = result XOR i XOR nums[i]。
  4. 走完後 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)本文採用