[Leetcode]41. First Missing Positive

题目描述

Given an unsorted integer array, find the smallest missing positive integer.

例子

例子 1

Input: [1,2,0]
Output: 3

例子 2

Input: [3,4,-1,1]
Output: 2

例子 3

Input: [7,8,9,11,12]
Output: 1

要求

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

题目思路

看到要求线性时间和常数空间，首先想到基本是要在数组内部做文章。考虑以下例子：

[4, 3, 2, 1, 5, 6]
[4, 3, 2, 1, 5, 7]
[4, 3, 2, -1, 5, 6]
[4, 3, 2, 1, 5, -6]

观察一下可以发现，如果数组内部包含了所有正数的话，正数的范围应该是在 1 ～ n 里面，而且最大不会超过 n；所以有几类数字我们可以不用关注：0，负数，超过 n 的正数；然后发现数字和 n 有关系的话，可以想到利用数组的位置来作为标志存放遇到的正数。比如将上面第三个例子排列成如下方式：

[4, 3, 2, -1, 5, 6]

// after
[x, 2, 3, 4, 5, 6]

这样我们只要扫描遇到 index（+1）和其元素不相同的第一个就可以发现缺失的第一个正数了；因此只需要扫描一遍数组，将所有 1 ～ n 范围内的正数放在正确的位置，注意每次更换一次都要确保换回来的数字要么是正确的，要么是不需要的数字，否则要继续更换，然后再扫描一遍就可以知道结果，代码如下。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        int index = 0;
        while (index < n) {
            while (nums[index] > 0 && nums[index] <= n && nums[index] != index + 1) {
                int correct_index = nums[index] - 1;
                if (nums[index] == nums[correct_index]) {
                    break;
                }
                swap(nums[index], nums[correct_index]);
            }
            index++;
        }

        int first_missing_positive = n + 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] != (i + 1)) {
                first_missing_positive = i + 1;
                break;
            }
        }

        return first_missing_positive;
    }
};

时间复杂度： O(n)
空间复杂度： O(1)