題目：

Given an unsorted integer array, find the first missing positive integer.

For example,
Given?[1,2,0]?return?3,
and?[3,4,-1,1]?return?2.

Your algorithm should run in?O(n) time and uses constant space.

鏈接： ? http://leetcode.com/problems/first-missing-positive/

題解：

找到第一個missing positive，要求O(n)。首先就想到了像sort colors一樣的swap方法。把invalid case都swap到array的后部，兩次pass就可以找到first mission positive。?

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {public int firstMissingPositive(int[] nums) {if(nums == null || nums.length == 0)return 1;int lo = 0, hi = nums.length - 1;while(lo <= hi) {if(nums[lo] <= 0 || nums[lo] > hi) //invalid caseswap(nums, lo, hi--);else if (nums[lo] == lo + 1)lo++;else if(nums[lo] < lo + 1) // duplicates in lower indexswap(nums, lo, hi--);else {if(nums[lo] == nums[nums[lo] - 1]) // duplicates in high indexswap(nums, lo, hi--);elseswap(nums, lo, nums[lo] - 1); // swap to correct position }}for(int i = 0; i < nums.length; i++)if(nums[i] != i + 1)return i + 1;return nums.length + 1;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;} }

?

更簡潔的寫法是

public class Solution {public int firstMissingPositive(int[] nums) {if(nums == null || nums.length == 0)return 1;for(int i = 0; i < nums.length; i++) {if(nums[i] > 0 && nums[i] < nums.length && nums[i] != nums[nums[i] - 1]) {swap(nums, i, nums[i] - 1);i--; // recheck newly swaped value at position i } } for(int i = 0; i < nums.length; i++)if(nums[i] != i + 1)return i + 1;return nums.length + 1;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;} }

?

二刷:

二刷依然寫得比較復(fù)雜， reference里面有很多很簡潔的寫法，要加以學(xué)習(xí)。思路是利用排除法和雙指針夾逼，使用類似于sort colors里面的swap()來在O(n)的時間和O(1)的space遍歷數(shù)組，我們有一下幾種case:

當(dāng) nums == null || nums.length == 0的時候，我們返回最小正整數(shù) 1

設(shè)定lo = 0， hi = nums.length - 1

當(dāng)nums[lo] <= 0或者nums[lo] > hi的時候，這兩種情況為invalid，我們肯定能在數(shù)組中找到更合適的元素，我們swap(nums, lo, hi)，然后hi--

接下來，當(dāng)nums[lo] = lo + 1的時候，這時候是valid condition，我們增加lo = lo + 1

假如nums[lo] < lo +1，經(jīng)歷過上面的條件以后，我們可以肯定nums[lo] - 1 >= 0并且nums[lo] - 1 < lo，說明我們之前已經(jīng)處理過nums[lo] - 1這個index，并且找到了一個合理的值。那么現(xiàn)在我們可以判斷出這里的nums[lo]是一個duplicate，我們執(zhí)行 swap(nums, lo, hi--)把它移動到數(shù)組末尾去。這個條件說明在lo這個index出現(xiàn)了duplicate。

現(xiàn)在剩下的情況是我們的nums[lo] > lo + 1，并且nums[lo] < hi。這時候算是我們的一般情況，我們要把這個nums[lo]交換到他應(yīng)該處于的為止，并且這個位置的index > lo而且index < hi。?因為在理想的情況下，我們的index與值的對應(yīng)關(guān)系應(yīng)該是i = nums[i] - 1，所以我們要嘗試把nums[lo]換到nums[lo] - 1這個位置。但在這個時候我們需要進(jìn)行一個判斷， 就是假如 lo = 2， nums[lo] = 5， 假設(shè)nums[nums[lo] - 1] = nums[4]也等于5怎么辦? 假如我們交換的話，那程序就會陷入死循環(huán)。這個時候我們判斷出這里當(dāng)前的nums[lo]其實也是一個duplicate，是higher index ?”nums[lo] - 1"這個位置的duplicate。所以我們依然執(zhí)行swap(nums, lo, hi--)，把這個數(shù)字交換到當(dāng)前的尾部去。

最后的情況就是nums[lo] != nums[nums[lo] - 1]， 我們可以放心大膽地執(zhí)行swap(nums, lo, nums[lo] - 1)，讓循環(huán)去判斷接下來的情況。

最后我們需要從頭算一遍i從0到nums.length - 1， nums[i]是否等于 i + 1，假如不等，即可返回i+1，否則我們要返回nums.length + 1。

可以簡化的地方有很多很多很多。希望三刷的時候能理清邏輯，大大簡化。

Java:

Time Complexity - O(n)， Space Complexity - O(1)

?

public class Solution {public int firstMissingPositive(int[] nums) {if (nums == null || nums.length == 0) {return 1;}int lo = 0, hi = nums.length - 1;while (lo <= hi) {if(nums[lo] <= 0 || nums[lo] > hi) {swap(nums, lo, hi--);} else if (nums[lo] == lo + 1) {lo++;} else if (nums[lo] < lo + 1) {swap(nums, lo, hi--);} else if (nums[lo] == nums[nums[lo] - 1]) {swap(nums, lo, hi--);} else {swap(nums, lo, nums[lo] - 1);}}for (int i = 0; i < nums.length; i++) {if (nums[i] != i + 1) {return i + 1;}}return nums.length + 1;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;} }

?

把很多條件都放在了一起，少了幾行。 還可以設(shè)置一個index變量來避免第二次循環(huán)的查找，留給三刷了。

public class Solution {public int firstMissingPositive(int[] nums) {if (nums == null || nums.length == 0) {return 1;}int lo = 0, hi = nums.length - 1;while (lo <= hi) {if (nums[lo] == lo + 1) {lo++;} else if(nums[lo] <= 0 || nums[lo] > hi || nums[lo] < lo + 1 || nums[lo] == nums[nums[lo] - 1]) {swap(nums, lo, hi--);} else {swap(nums, lo, nums[lo] - 1);}}for (int i = 0; i < nums.length; i++) {if (nums[i] != i + 1) {return i + 1;}}return nums.length + 1;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;} }

?

?

題外話:

1/23/2016，現(xiàn)在我家已經(jīng)徹底被大雪封住了。有生以來從來沒見過這么大的雪，還在繼續(xù)下著。我家的門在一個走廊里，整個走廊現(xiàn)在都是30厘米左右高的雪。出去走廊走到外面的話，雪都累積到了大腿根部。幸好之前屯了不少糧食，現(xiàn)在還可以在家里吃鴛鴦火鍋(小肥羊辣湯/海底撈酸菜魚湯)。 據(jù)說有20萬戶斷電，希望大家都平安吧。

?

三刷:

用得二刷邏輯。

Java:

public class Solution {public int firstMissingPositive(int[] nums) {if (nums == null || nums.length == 0) return 1;int lo = 0, hi = nums.length - 1;while (lo <= hi) {if (nums[lo] > hi || nums[lo] <= 0) swap(nums, lo, hi--);else if (nums[lo] == lo + 1) lo++;else if (nums[lo] < lo + 1) swap(nums, lo, hi--);else if (nums[lo] == nums[nums[lo] - 1]) swap(nums, lo, hi--);else swap(nums, lo, nums[lo] - 1);}for (int i = 0; i < nums.length; i++) {if (nums[i] != i + 1) return i + 1;}return nums.length + 1;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;} }

?

Reference:

https://leetcode.com/discuss/20385/concise-o-n-solution

https://leetcode.com/discuss/32761/clear-java-solution

https://leetcode.com/discuss/60525/100%25-fast-elegant-java-index-based-solution-with-explanation

https://leetcode.com/discuss/28531/o-1-space-java-solution

https://leetcode.com/discuss/24013/my-short-c-solution-o-1-space-and-o-n-time

?

總結(jié)

以上是生活随笔為你收集整理的41. First Missing Positive的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。