題目描述

缺失的第一個正數(shù)

給你一個未排序的整數(shù)數(shù)組 nums ，請你找出其中沒有出現(xiàn)的最小的正整數(shù)。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解法

如果本題沒有額外的時空復雜度要求，那么就很容易實現(xiàn)：

• 我們可以將數(shù)組所有的數(shù)放入哈希表，隨后從 111 開始依次枚舉正整數(shù)，并判斷其是否在哈希表中；
• 我們可以從 111 開始依次枚舉正整數(shù)，并遍歷數(shù)組，判斷其是否在數(shù)組中。

如果數(shù)組的長度為 N，那么第一種做法的時間復雜度為 O(N)，空間復雜度為 O(N)；第二種做法的時間復雜度為 O(N^2)，空間復雜度為 O(1)。但它們都不滿足時間復雜度為 O(N) 且空間復雜度為 O(1)。

但是我們可以利用給定數(shù)組中的空間來存儲一些狀態(tài)。也就是說，如果題目給定的數(shù)組是不可修改的，那么就不存在滿足時空復雜度要求的算法；但如果我們可以修改給定的數(shù)組，那么是存在滿足要求的算法的。

對于上面中提到的第一種做法：

我們可以將數(shù)組所有的數(shù)放入哈希表，隨后從 111 開始依次枚舉正整數(shù)，并判斷其是否在哈希表中。

仔細想一想，我們?yōu)槭裁匆褂霉１?？這是因為哈希表是一個可以支持快速查找的數(shù)據(jù)結(jié)構(gòu)：給定一個元素，我們可以在 O(1)的時間查找該元素是否在哈希表中。因此，我們可以考慮將給定的數(shù)組設(shè)計成哈希表的「替代產(chǎn)品」。

**實際上，對于一個長度為 N 的數(shù)組，其中沒有出現(xiàn)的最小正整數(shù)只能在 [1,N+1] 中。**這是因為如果 [1, N] 都出現(xiàn)了，那么答案是 N+1，否則答案是 [1,N] 中沒有出現(xiàn)的最小正整數(shù)。

這樣一來，我們將所有在 [1, N]范圍內(nèi)的數(shù)放入哈希表，也可以得到最終的答案。而給定的數(shù)組恰好長度為 N，這讓我們有了一種將數(shù)組設(shè)計成哈希表的思路：

我們對數(shù)組進行遍歷，對于遍歷到的數(shù) x，如果它在[1,N] 的范圍內(nèi)，那么就將數(shù)組中的第 x?1個位置（注意：數(shù)組下標從 0開始）打上「標記」。在遍歷結(jié)束之后，如果所有的位置都被打上了標記，那么答案是 N+1，否則答案是最小的沒有打上標記的位置加 1。

那么如何設(shè)計這個「標記」呢？由于數(shù)組中的數(shù)沒有任何限制，因此這并不是一件容易的事情。但我們可以繼續(xù)利用上面的提到的性質(zhì)：由于我們只在意 [1, N] 中的數(shù)，因此我們可以先對數(shù)組進行遍歷，把不在 [1, N] 范圍內(nèi)的數(shù)修改成任意一個大于 N 的數(shù)（例如 N+1）。這樣一來，數(shù)組中的所有數(shù)就都是正數(shù)了，因此我們就可以將「標記」表示為「負號」。算法的流程如下：

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

java代碼：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 將負數(shù)變?yōu)閚 + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        // 將元素<=n對應(yīng)的位置變?yōu)樨摂?shù)，表示在該位置的元素在1 ~ n范圍內(nèi)
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <=  n) {
                // 注意由于有相同的元素，有可能原來nums[num - 1]的元素由正數(shù)變負數(shù)，然后又變?yōu)檎龜?shù)，所以使用絕對值的負數(shù)
                nums[num - 1] = - Math.abs(nums[num - 1]);
            }
        }
        // 返回第一個大于0的元素下標 + 1
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

復雜度文章來源地址http://www.zghlxwxcb.cn/news/detail-798180.html

• 時間復雜度：O(N)，其中 N 為數(shù)組的長度
• 空間復雜度：O(1)。

到了這里，關(guān)于LeetCode 41 缺失的第一個正數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！