041.First Missing Positive
难度:Hard
刷题内容
原题连接
- https://leetcode.com/problems/first-missing-positive/
内容描述
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
˼· **- ʱ�临�Ӷ�: O(n)*- �ռ临�Ӷ�: O(1)***
�տ�ʼ��Ŀ����˼������ˣ�֮�������AC�ˡ���ʵ内容描述内容描述�������Ĵ���ռ䣬Ӧ�û������뵽��ֱ�� hash �����У内容描述ǿ��Ա������飬内容描述�1内容描述��ĵ�һ������1����2���ڣ内容描述�ĵڶ���λ�ӣ内容描述�
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if(!nums.size())
return 1;
for(int i = 0;i < nums.size();)
{
if(nums[i] < nums.size() && nums[i] != nums[nums[i] - 1])
swap(nums[i],nums[nums[i] - 1]);
else
++i;
}
for(int i = 0;i < nums.size();++i)
if(nums[i] != i + 1)
return i + 1;
return nums.size() + 1;
}
};
