題目描述

給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。

請你實現時間復雜度為 O(n) 并且只使用常數級別額外空間的解決方案。

示例 1：

輸入：nums = [1,2,0]
輸出：3
解釋：范圍 [1,2] 中的數字都在數組中。

示例 2：

輸入：nums = [3,4,-1,1]
輸出：2
解釋：1 在數組中，但 2 沒有。

示例 3：

輸入：nums = [7,8,9,11,12]
輸出：1
解釋：最小的正數 1 沒有出現。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

解法一

思路：

來自官方解答。實際上，對于一個長度為 N 的數組，其中沒有出現的最小正整數只能在 [1,N+1] 中。這是因為如果 [1,N] 都出現了，那么答案是 N+1，否則答案是 [1,N] 中沒有出現的最小正整數。我們對數組進行遍歷，對于遍歷到的數 x，如果它在 [1,N] 的范圍內，那么就將數組中的第 x?1 個位置（注意：數組下標從 0 開始）打上「標記」。在遍歷結束之后，如果所有的位置都被打上了標記，那么答案是 N+1，否則答案是最小的沒有打上標記的位置加 1。

由于我們只在意 [1,N] 中的數，因此我們可以先對數組進行遍歷，把不在 [1,N] 范圍內的數修改成任意一個大于 N 的數（例如 N+1）。這樣一來，數組中的所有數就都是正數了，因此我們就可以將「標記」表示為「負號」。算法的流程如下：

• 我們將數組中所有小于等于 0 的數修改為 N+1；
• 我們遍歷數組中的每一個數 x，它可能已經被打了標記，因此原本對應的數為 ∣x∣，其中 ∣∣ 為絕對值符號。如果 ∣x∣∈[1,N]，那么我們給數組中的第 ∣x∣?1 個位置的數添加一個負號。注意如果它已經有負號，不需要重復添加；
• 在遍歷完成之后，如果數組中的每一個數都是負數，那么答案是 N+1，否則答案是第一個正數的位置加 1。

代碼：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

解法二

思路：

來自官方解答。除了打標記以外，我們還可以使用置換的方法，將給定的數組「恢復」成下面的形式：

如果數組中包含 x∈[1,N]，那么恢復后，數組的第 x?1 個元素為 x。

在恢復后，數組應當有 [1, 2, ..., N] 的形式，但其中有若干個位置上的數是錯誤的，每一個錯誤的位置就代表了一個缺失的正數。以題目中的示例二 [3, 4, -1, 1] 為例，恢復后的數組應當為 [1, -1, 3, 4]，我們就可以知道缺失的數為 2。

那么我們如何將數組進行恢復呢？我們可以對數組進行一次遍歷，對于遍歷到的數 x=nums[i]，如果 x∈[1,N]，我們就知道 x 應當出現在數組中的 x?1 的位置，因此交換 nums[i] 和 nums[x?1]，這樣 x 就出現在了正確的位置。在完成交換后，新的 nums[i] 可能還在 [1,N] 的范圍內，我們需要繼續進行交換操作，直到 x∈/[1,N]。

注意到上面的方法可能會陷入死循環。如果 nums[i] 恰好與 nums[x?1] 相等，那么就會無限交換下去。此時我們有 nums[i]=x=nums[x?1]，說明 x 已經出現在了正確的位置。因此我們可以跳出循環，開始遍歷下一個數。

由于每次的交換操作都會使得某一個數交換到正確的位置，因此交換的次數最多為 N，整個方法的時間復雜度為 O(N)。

代碼：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}