LeetCode-41-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.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

• 1 假设数组中不包含1, 那么其缺失的最小正整数是1

• 2 简单的解题思路就是排序, 然后从1开始遍历, 但是其时间复杂度到了O(nlogn + n)

• 3 假设求取的值是t, 那么说明在长度为n的数组中存在有[1,t-1]; 假设该题给出长度为n的数组, 那么结果可能的值为[1,n+1]

  • 因为t-1 <= n, 则t <= n+1

• 4 如果仅仅需要在n个数中遍历, 那么时间复杂度可以达到O(N)的级别; 第一次遍历获取[1,n]的是是否存在, 第二次找到第一个不存在的值

• 5 因为空间复杂度要求是常数级, 索引只能在原地进行数据的保存, 可以使用D[n]的正负来表示n值是否存在(负数、0、大于n的值都不需要考虑)

C++实现

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

        bool contain1 = false;
        for(int i = 0; i < n; i++)
            if(nums[i] == 1)
                contain1 = true;
            else if(nums[i] <= 0 || nums[i] > n)
                nums[i] = 1;
            //因为需要用正负数来表示是否存在, 并且负数、0、大于n的值都不需要考虑, 所以设置为1

        if(!contain1) return 1;         //不包含1, 那么结果就是1
        if(n == 1)  return 2;           //如果长度仅为1, 并且包含了数1, 那么结果是2

        for(int i = 0; i < n; i++)
        {
            int t = abs(nums[i]);
            if(t == n)
                nums[0] = -1 * abs(nums[0]);             //负数表示存在
            else
                nums[t] = -1 * abs(nums[t]);
        }

        for(int i = 1; i < n; i++)
            if(nums[i] > 0)
                return i;
        if(nums[0] > 0) return n;
        return n+1;
    }
};