題目描述
給定一個(gè)未排序的整數(shù)數(shù)組声搁，找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。
示例 1:
輸入: [1,2,0]
輸出: 3
示例 2:
輸入: [3,4,-1,1]
輸出: 2
示例 3:
輸入: [7,8,9,11,12]
輸出: 1
說(shuō)明:
你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)氯庆，并且只能使用常數(shù)級(jí)別的空間裁良。
知識(shí)點(diǎn)
數(shù)組
Qiang的思路
因?yàn)樽罱K關(guān)注的是正整數(shù)，所以這個(gè)問(wèn)題可以對(duì)非正數(shù)不予考慮腾夯。
首先通過(guò)遍歷數(shù)組颊埃，將每一個(gè)正數(shù)調(diào)至位置為其數(shù)值-1的位置，這樣我們便可以得到一個(gè)正數(shù)有序并且所在位置與該數(shù)-1相同的數(shù)組蝶俱。通過(guò)遍歷該數(shù)組找到第一個(gè)下標(biāo)+1與該位置數(shù)值不同的元素班利，這個(gè)下標(biāo)+1便是缺失的第一個(gè)正數(shù)。
PS：需要對(duì)長(zhǎng)度為0的特殊情況進(jìn)行考慮榨呆。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(nums.size()==0)
return 1;
for(int i=0;i<nums.size();i++)
while(nums[i]-1>=0 && nums[i]-1<nums.size() && nums[nums[i]-1]!=nums[i])
swap(nums[i], nums[nums[i]-1]);
int result=0;
for(; result<nums.size(); result++)
if(nums[result]!=result+1)
break;
return result+1;
}
};
作者原創(chuàng)罗标，如需轉(zhuǎn)載及其他問(wèn)題請(qǐng)郵箱聯(lián)系：lwqiang_chn@163.com。
個(gè)人網(wǎng)站：https://www.myqiang.top积蜻。
