题目描述

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

样例

输入: [1,2,0]
输出: 3

输入: [3,4,-1,1]
输出: 2

输入: [7,8,9,11,12]
输出: 1

提示：

你的算法的时间复杂度应为$O(n)$，并且只能使用常数级别的额外空间。

算法分析

桶排序思想（注意这里不能用额外的空间，只能原地操作）

• 1、数组长度是n，确保通过某种规律的交换使得,nums[0] = 1,nums[1] = 2 … nums[n - 1] = n，必须下标与对应的数值保持一致

• 2、若存在不在[1,n]区间的数时，则表示该数一定会在原数组占空间，且占到不能被对应的位置上，因此从小到大枚举，若nums[i] != i + 1，则表示i + 1这个数是第一个缺失的正数，若都没有缺失，那么n + 1就是第一个缺失的正数

• 3、1操作所说的通过某种规律的交换是指：如果该位置的数值与该坐标不对应，即nums[i] != i + 1时，交换i和nums[i] - 1位置的数（其中nums[i] - 1是nums[i]需要填进去的位置），例如3 2 1，交换后变成1 2 3

时间复杂度 $O(n)$

Java 代码

class Solution {
    static void swap(int[] nums,int a,int b)
    {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i = 0;i < n;i ++)
        {
            while(nums[i] > 0 && nums[i] <= n && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1])
                swap(nums,i,nums[i] - 1);
        }

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