# 資訊

:::info
- Question: 41. First Missing Positive
- From: Leetcode Daily Challenge 2024.03.26
- Difficulty: Hard
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

Given an unsorted integer array `nums`. Return the smallest positive integer that is not present in `nums`.

You must implement an algorithm that runs in $O(n)$ time and uses $O(1)$ auxiliary space.

> Example 1:
:::success
- Input: `nums = [1,2,0]`
- Output: 3
- Explanation: The numbers in the range `[1,2]` are all in the array.
:::

> Example 2:
:::success
- Input: `nums = [3,4,-1,1]`
- Output: 2
- Explanation: 1 is in the array but 2 is missing.
:::

> Example 3:
:::success
- Input: `nums = [7,8,9,11,12]`
- Output: 1
- Explanation: The smallest positive integer 1 is missing.
:::

> Constraints:
:::success
- 1 <= `nums.length` <= $10^5$
- $-2^{31}$ <= `nums[i`] <= $2^{31} - 1$
:::

---

# 解法

## 概念

久違了，在最忙的幾天給我塞 hard，真有你的 leetcode！

這題感覺跟昨天很像，一樣是透過 mark 成負的來當作 flag 去做後續判斷

因為題目說要找 first missing positive，當題目給大小為 `n` 的 array 時，可以猜到解答肯定是 `[1:n+1]` 這段區間，而 `n+1` 會出現在當 array 剛好就是 `[1, 2, ..., n]` 的時候

所以在一開始我把整條 array traverse 過一次，把在我關心的元素 (aka `[1:n]`) 以外全部置換成 `n+1`，其實只是要換成一個不會在 `[1:n]` 之中，等等可以判斷的數字即可

接著重新 traverse 過這條 array，從第零個開始，我去取該位置的數值，這時候得到的結果應該就會是 [1:n+1]，而 `n+1` 正好就是那些我不想關心的元素，可以直接忽略（第 12 - 13 行），再來第 14 行是要把該數值變成 0-index，最後就把對應 index 的數值改成負的（第 15 - 16 行），代表該 index + 1 是出現在 `nums` 過的，而為什麼第 11 行要用絕對值取值也是這個原因

最後第 18 - 21 行就是在找第一個不為負的 index 是誰，其加一就會是第一個沒出現在 `nums` 的正數

如果都沒有，代表 `nums = [1:n]`，那就是要回傳 `n+1`（第 23 行）

## 程式碼

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # Reform nums: each element in range [1:n+1]
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n: # Those element I do not care
                nums[i] = n + 1

        # Traverse nums and mark all existing numbers
        for i in range(n):
            num = abs( nums[i] )
            if num > n: # Those element I do not care
                continue
            num -= 1    # To fit the 0-index
            if nums[num] > 0:   # Those element I do care ([1:n])
                nums[num] = -1 * nums[num]  # Mark negative as the (index + 1) "in" nums

        # Find the first missing positive
        for i in range(n):
            if nums[i] > 0:    # Positive means that (index + 1) is not in nums
                return i+1

        return n+1              # [1:n] are all in nums, the first missing positive is n+1

---

# 複雜度

## 時間複雜度

首先排除我不關心的 element 花了一次 $O(n)$，traverse 所有 element 並 mark 成負的那時候又花了一次 $O(n)$，最後尋找 first missing positive 也花了一次 $O(n)$，整體是 $O(3n) = O(n)$

題目的 hint 說「記得 $O(2n) = O(n)$」，說不定其他人比較快是因為這樣？


## 空間複雜度

大多數的空間需求都在 `nums` 裡面處理完，所以跟題目要求一樣是 $O(1)$