First Missing Positive
首先悼沿，實(shí)在受不了微信公眾號(hào)后臺(tái)對(duì)markdown的支持潘鲫，查找了很多關(guān)于微信公眾號(hào)排版的文章捺疼，包括池建強(qiáng)老師在知乎上地回答窃植，池老師說微信后臺(tái)對(duì)于代碼的支持很差，真是深有體會(huì)悯森。
從這篇文章開始宋舷，在文章中只提供文章題目的引用描述，題解移動(dòng)到查看原文中瓢姻，請(qǐng)各位見諒祝蝠。
今天是一道在LeetCode上標(biāo)記為Hard的題目，Acceptance為22.9%的題目，雖然知道思路之后會(huì)發(fā)現(xiàn)其實(shí)較為簡(jiǎn)單绎狭。
題目如下：
Given an unsorted integer array, find the first missing positive integer.
For example,Given[1,2,0]return3,
and[3,4,-1,1]return2.
Your algorithm should run in O(n) time and uses constant space.
其實(shí)细溅，如果題目中不限制constant space，可以很容易解決這個(gè)問題儡嘶，只要使用一個(gè)HashMap<Integer, Boolean>記錄每一個(gè)數(shù)字是否出現(xiàn)過喇聊，然后從1開始，用HashMap.get(Integer)蹦狂，當(dāng)獲得的值是null時(shí)誓篱，就是我們要找的值。
但是題目中限制了必須使用constant space凯楔，就不能采用這種方法窜骄，那么應(yīng)該怎么做呢。
思路如下：
數(shù)組本身也可以作為一個(gè)map使用摆屯，即以數(shù)組的下標(biāo)為鍵邻遏，以該下標(biāo)的值為map的值，這樣就可以把數(shù)組當(dāng)做是map來看虐骑。代碼如下：
C++版
class Solution
{
public:
int firstMissingPositive(int A[], int n)
{
for(int i = 0; i < n; ++ i)
while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
swap(A[i], A[A[i] - 1]);
for(int i = 0; i < n; ++ i)
if(A[i] != i + 1)
return i + 1;
return n + 1;
}
};
java
public class Solution {
public int firstMissingPositive(int[] nums) {
for(int i = 0; i < nums.length; i++){
if(nums[i] != i + 1){
int num = nums[i];
while(num < nums.length + 1 && num > 0 && nums[num - 1] != num){
int temp = nums[num - 1];
nums[num - 1] = num;
num = temp;
}
}
}
for(int i = 0; i < nums.length; i++){
if(nums[i] != i + 1)
return i + 1;
}
return nums.length + 1;
}
}
如果覺得文章有幫助的話准验，不妨關(guān)注一下本公眾號(hào)，當(dāng)然也希望能幫作者推廣一下富弦，更多人關(guān)注我也會(huì)更有動(dòng)力沟娱，在此先謝過了。
關(guān)注我
