題目
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.
分析
這題是hard慰丛，但是感覺(jué)并不是很難啊骗随。首先使用一個(gè)數(shù)組記錄每個(gè)正整數(shù)是否出現(xiàn)過(guò)。然后從小到大檢查該數(shù)組篮条，輸出第一個(gè)未出現(xiàn)的數(shù)字即可。
實(shí)現(xiàn)
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(nums.empty()) return 1;
bool flag[nums.size()] = {false};
for(int i=0; i<nums.size(); i++){
if(nums[i]>0 && nums[i]<nums.size()+1)
flag[nums[i]-1] = true;
}
for(int i=0; i<nums.size(); i++){
if(!flag[i])
return i+1;
}
return nums.size()+1;
}
};
思考
在做題的過(guò)程中發(fā)現(xiàn)税灌，使用auto比使用int型下標(biāo)來(lái)遍歷vector要慢械念。所以也許使用的時(shí)候要多注意。
