[LeetCode解題攻略] 41. First Missing Positive

題目描述

給定一個未排序的整數數組 nums，找出其中的最小的缺失的正整數。

• 必須設計一個時間複雜度為 O(n) 的解法，並且空間複雜度為 O(1) 。

範例 1

輸入: nums = [1,2,0]
輸出: 3

輸入: nums = [3,4,-1,1]
輸出: 2

範例 3

輸入: nums = [7,8,9,11,12]
輸出: 1

解題思路

1. 我們需要找到數組中最小的缺失正整數。
2. 題目要求時間複雜度為 O(n)，這意味著傳統的排序方法（O(n log n)）不適用。
3. 同時，要求只使用常數空間，這限制了我們不能使用額外的數組來儲存結果。

基於以上限制，解法核心是將數組作為哈希表來操作，透過將元素放在正確的位置來確定缺失的數字。

解法一：原地雜湊（Cyclic Sort）

核心思想

將每個數字放到對應的索引位置，例如：

• 如果數字為 x，且 1 <= x <= n（n 是數組長度），我們應該將 x 放在索引 x-1 的位置。

最後，掃描數組，第一個數字不符合其索引的，就是缺失的正整數。

步驟

1. 遍歷數組，將每個數字放到正確的位置：
2. • 如果 nums[i] 的值在 [1, n] 範圍內，且 nums[i] != nums[nums[i] - 1]，則交換 nums[i] 與 nums[nums[i] - 1]。
2. 再次遍歷數組，找到第一個 nums[i] != i + 1 的位置，返回 i + 1。
3. 如果數組中所有數字都在正確位置，則返回 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. 利用數組本身作為狀態標記：
2. • 將數組中的每個數字（如果在範圍內 1 <= x <= n）標記到對應的索引位置。
   • 我們通過將數字對應位置的值設為負數來標記它已經出現過。
2. 掃描標記結果：
3. • 如果某個位置的值仍為正，說明該索引的數字缺失。

步驟

1. 遍歷數組，將 1 <= nums[i] <= n 的數字標記到對應索引。
2. 再次遍歷數組，找到第一個值為正的索引，返回其對應數字 i + 1。
3. 如果所有位置都已標記，則返回 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)
• • 使用數組本身作為標記，未使用額外的儲存空間。

結論

1. 原地哈希法 是解決該問題的經典解法，特別適合實現簡單的場景。
2. 標記法 更適合處理帶有範圍約束的問題，尤其是當需要快速排除無效數字時。

兩種解法都滿足題目對時間和空間的要求，可以根據需求選擇適合的實現方式！