Skip to content

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;
    }
};


回到顶部