缺失的第一个正整数：原地哈希找数

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

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

是什么？

为排序数组找未出现的最小正整数

怎么做？

使用原地哈希查找

思考

七七原本思路是像昨天刷的题那样子左右两边查找，但是那样子需要涉及排序，而排序就到了对数复杂度了，显然不合题意，但是还是看看吧

import java.util.Arrays;

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int[] copy = Arrays.copyOf(nums, n);
        Arrays.sort(copy);

        for (int i = 1; i <= n; i++) {
            if (i - 1 < copy.length && copy[i - 1] == i) {
                continue;
            } else {
                return i;
            }
        }
        return n + 1;
    }
}

当然这个代码去运行也是错的，哈哈哈

代码

/**
 * 找出数组中未出现的最小正整数
 * @param nums 整数数组，可能包含负数、零和重复元素
 * @return 最小的未出现的正整数
 */
class Solution {
    /**
     * 查找未出现的最小正整数
     * @param nums 整数数组，可能包含负数、零和重复元素
     * @return 最小的未出现的正整数
     */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 将每个正整数放到其应在的位置
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int correctIndex = nums[i] - 1;
                int temp = nums[i];
                nums[i] = nums[correctIndex];
                nums[correctIndex] = temp;
            }
        }

        // 查找第一个未出现在正确位置的正整数
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

因为不是很难理解所以注释交给灵宝写啦