题目描述

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

题目分析

位置置换，哈希表的思想.
数组大小为 n，则缺失的第一个正数在 [1, n + 1] 内
在数组内进行位置置换，保证数字 x 放在 x – 1 的位置上（超出范围则不做处理）。
最后从头遍历一次，第一个不符合规则的位置，即是缺少的正数。
如果 n 个数字全都符合规则，则答案是 n + 1
时间复杂度 O(n), 空间复杂度 O(1)

Java

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        while (x <= n && x > 0 && nums[x - 1] != x) {
            int temp = nums[x - 1];
            nums[x - 1] = x;
            nums[i] = temp;
            x = nums[i];
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

Kotlin

fun firstMissingPositive(nums: IntArray): Int {
    val n = nums.size
    for (i in nums.indices) {
        var x = nums[i]
        while (x in 1..n && nums[x - 1] != x) {
            val temp = nums[x - 1]
            nums[x - 1] = x
            nums[i] = temp
            x = nums[i]
        }
    }
    for (i in nums.indices) {
        if (nums[i] != i + 1) {
            return i + 1
        }
    }
    return n + 1
}