1 題目

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

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

2 解法

最笨的方法是從1開始試, 看1在數組里面是否出現過, 2, 3, ....不過時間復雜度是.

2.1 hash

可以考慮用hash, 遍歷數組, 把每個元素的值作為key, 遍歷完數組之后再從1開始看是否在hash里面. 但是這樣做會額外申請一個hash容器, 這樣就不是常數級額外空間了, 而是. 于是考慮利用原數組構造所需hash表. 首先要明確一點, 假設數組的元素個數是n, 會有兩種情況, 如果數組正好囊括了所有1 ~ n的所有正整數, 那么不存在的最小正整數就是n + 1, 但凡有一個元素值不在1 ~ n中, 所求結果就在[1, n]中. 可以考慮遍歷數組, 如果元素值value在[1, n]中, 那么就在對應nums[value - 1](n個元素下標從0開始, nums[0]代表第一個元素)標記一下, 證明value是出現過的, 這樣最后再遍歷nums, 發現第一個沒有標記上的元素的索引 + 1就是所找的最小正整數. 但是怎么標記呢? 比如元素value在[1, n] 中, 那么就要對nums[value - 1]進行標記, 但是還不能丟失該元素的值信息(比如nums[value - 1]也在[1, n]里面, 你改成n + 2的話就會丟失原有的信息了), 所以考慮到設置成負值. 這樣結尾遍歷的時候, 小于零的話證明這個位置被別人標記過, 也就是占位的正整數出現過, 那么大于0的值的下標 + 1就是第一個結果. 如果遍歷到最后還沒有返回值, 那么就是n + 1, 要這么做的話首先要保證所有元素都為正的, 那么就把非正元素設置為n + 1.

代碼:

int firstMissingPositive(vector<int>& nums) {int nums_size = nums.size();for (int &num: nums) {if (num <= 0) {num = nums_size + 1;}}for (int i = 0; i < nums_size; i ++) {if (nums[i] <= 0) {nums[i] = nums_size + 1;}}for (int i = 0; i < nums_size; i ++) {int ele_abs = abs(nums[i]);if (ele_abs <= nums_size) {nums[ele_abs - 1] = -abs(nums[ele_abs - 1]);}}for (int i = 0; i < nums_size; i ++) {if (nums[i] > 0)return i + 1;}return nums_size + 1; }

2.2 置換法

總結

以上是生活随笔為你收集整理的leetcode41 --- firstMissingPositive的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。