問(wèn)題描述
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.
問(wèn)題分析
這是一道hard題，自己沒(méi)有思路TAT椰弊，在網(wǎng)上搜了解答
分析題意
- 要找的是第一個(gè)不存在的正數(shù)蝗锥，那么對(duì)于長(zhǎng)度為n的輸入捍歪，非正數(shù)和大于n的數(shù)都是沒(méi)有用的。
- 要求用常數(shù)空間解決，因此不能另開(kāi)數(shù)組，而應(yīng)該在原數(shù)組上進(jìn)行操作，這時(shí)應(yīng)留意到本鸣，數(shù)組的下標(biāo)是0到n-1，與我們考慮的正數(shù)范圍1到n是一一對(duì)應(yīng)的硅蹦。
- 我們利用下標(biāo)作為標(biāo)記荣德，將數(shù)組中每個(gè)在1到n之間的元素item，放在nums[item-1]的位置童芹，然后第二次遍歷數(shù)組涮瞻，找到第一個(gè)nums[i] != i+1的位置，則i+1就是我們要找的first missing postive integer假褪。
做法
- 第一次遍歷數(shù)組饲宛，若nums[i]的值在1，n之間且nums[nums[i]-1] != nums[i]嗜价，則交換nums[nums[i]-1]和nums[i]艇抠。nums[nums[i]-1] != nums[i]包含兩層含義，1)如果nums[i] != i+1久锥，則nums[i]-1 != i家淤，那么nums[i]需要被調(diào)換到它應(yīng)該去的位置；如果nums[nums[i]-1] == nums[i]說(shuō)明待交換的兩個(gè)數(shù)字相等瑟由，則不需交換絮重，否則會(huì)死循環(huán)。需要注意的是，如果被換到nums[i]位置的數(shù)字依然符合交換條件青伤，那么需要繼續(xù)進(jìn)行交換督怜，也就是說(shuō)這里不是一個(gè)if判斷，而是一個(gè)while循環(huán)狠角。
- 第二次遍歷數(shù)組号杠，找到第一個(gè)nums[i] != i+1的位置，返回i+1丰歌。
復(fù)雜度分析
雖然這個(gè)思想還是蠻好理解姨蟋，但是在一個(gè)for循環(huán)里又出現(xiàn)了一個(gè)while循環(huán)，它的復(fù)雜度能是O(n)嗎立帖？其實(shí)是醬紫眼溶，算法復(fù)雜度應(yīng)該看的是基本操作的次數(shù)，在這個(gè)問(wèn)題里晓勇，基本操作指的是交換操作堂飞，而每次交換操作，都至少有一個(gè)數(shù)字去了它應(yīng)該去的地方绑咱，那么一個(gè)n長(zhǎng)度的數(shù)組绰筛，最多只需要n次交換操作，所以它的復(fù)雜度是O(n)的~
AC代碼
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
int i;
for (i = 0; i < n; i++){
while(nums[i] > 0 && nums[i] < n && nums[nums[i]-1] != nums[i]){
int tmp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = tmp;
}
}
for (i = 0; i < n; i++){
if (nums[i] != i+1)
break;
}
return i+1;
}
};
Runtime: 3 ms, which beats 70.66% of cpp submissions.
