41.First Missing Positive

Tags: Hard Array

Links: 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

Note:

Your algorithm should run in O(n) time and uses constant extra space.

---

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        for (int i = 0; i < nums.size(); ++i) {
            while (nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i] - 1] != nums[i])
                swap(nums[nums[i] - 1], nums[i]);
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i + 1) return i + 1;
        }

        return nums.size() + 1;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for First Missing Positive.
Memory Usage: 8.9 MB, less than 20.00% of C++ online submissions for First Missing Positive.

思路就是让下标i存储数字i+1，如果不符合就去交换数字，并且只需要考虑大于0的数字。

时间复杂度$O(n)$.

类似的题目：

• 287
• 41
• 268
• 136,137,260
• 448
• 645
• 565