題目描述
給定一個未排序的整數數組 nums，找出其中的最小的缺失的正整數。
- 必須設計一個時間複雜度為 O(n) 的解法，並且空間複雜度為 O(1) 。
範例 1
輸入: nums = [1,2,0]
輸出: 3
範例 2
輸入: nums = [3,4,-1,1]
輸出: 2
範例 3
輸入: nums = [7,8,9,11,12]
輸出: 1
解題思路
- 我們需要找到數組中最小的缺失正整數。
- 題目要求時間複雜度為 O(n)，這意味著傳統的排序方法（O(n log n)）不適用。
- 同時，要求只使用常數空間，這限制了我們不能使用額外的數組來儲存結果。
基於以上限制，解法核心是將數組作為哈希表來操作，透過將元素放在正確的位置來確定缺失的數字。
解法一：原地雜湊（Cyclic Sort）
核心思想
將每個數字放到對應的索引位置，例如：
- 如果數字為
x，且1 <= x <= n（n是數組長度），我們應該將x放在索引x-1的位置。
最後，掃描數組，第一個數字不符合其索引的，就是缺失的正整數。
步驟
- 遍歷數組，將每個數字放到正確的位置：
- 如果 nums[i] 的值在 [1, n] 範圍內，且 nums[i] != nums[nums[i] - 1]，則交換 nums[i] 與 nums[nums[i] - 1]。
- 再次遍歷數組，找到第一個
nums[i] != i + 1的位置，返回i + 1。 - 如果數組中所有數字都在正確位置，則返回
n + 1。
程式碼
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# 將每個數字放到正確的位置
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# 找出第一個缺失的正整數
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
時間與空間複雜度分析
- 時間複雜度：O(n)
- 每個數字最多只會被移動一次，因此整體時間為線性。
- 空間複雜度：O(1)
- 我們在原地操作數組，未使用額外的儲存空間。
解法二：標記法
核心思想
- 利用數組本身作為狀態標記：
- 將數組中的每個數字（如果在範圍內 1 <= x <= n）標記到對應的索引位置。
- 我們通過將數字對應位置的值設為負數來標記它已經出現過。
- 掃描標記結果：
- 如果某個位置的值仍為正，說明該索引的數字缺失。
步驟
- 遍歷數組，將
1 <= nums[i] <= n的數字標記到對應索引。 - 再次遍歷數組，找到第一個值為正的索引，返回其對應數字
i + 1。 - 如果所有位置都已標記，則返回
n + 1。
程式碼
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# 將不在範圍內的數字設為 n + 1
for i in range(n):
if nums[i] <= 0 or nums[i] > n:
nums[i] = n + 1
# 標記出現的數字
for i in range(n):
num = abs(nums[i])
if num <= n:
nums[num - 1] = -abs(nums[num - 1])
# 找出第一個缺失的正整數
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1
時間與空間複雜度分析
- 時間複雜度：O(n)
- 需要兩次遍歷數組。
- 空間複雜度：O(1)
- 使用數組本身作為標記，未使用額外的儲存空間。
結論
- 原地哈希法 是解決該問題的經典解法，特別適合實現簡單的場景。
- 標記法 更適合處理帶有範圍約束的問題，尤其是當需要快速排除無效數字時。
兩種解法都滿足題目對時間和空間的要求，可以根據需求選擇適合的實現方式！
