缺失的第一个正数

题目描述：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例：

输入：nums = [1,2,0]
输出：3

输入：nums = [4,5,6]
输出：1

题解

一上来拿到这个题我们就有很好的思路: 使用哈希表存放数组中的数, 然后从1开始枚举并不断比对numsMap

关键在于本题要求只能使用常数级别的额外空间, 这就比较麻烦。

其实这种题的思路比较死, 就是考虑数组中数据的特点, 将数组设计为哈希表。没有见到过这种题型的小伙伴会比较懵也是正常的, 多做几道类似的题目, 能举一反三就行。

把话说回本题上, 我们该如何设计这个数组? 这就要针对本题给出的条件来慢慢推理。

为什么把数组设计为哈希表?设我们有一个长度为 n 的数组, 如果 [1,n]中的所有数字都出现了一遍, 那么缺失的第一个正数就是n+1 ;如果[1,n]中的数字有没有出现的最小正整数, 那么答案就是ta。这样, 我们可以将[1,n]的范围内的数放入哈希表, 也能从中找到最终的答案。正好给定的数组的长度为n , 我们可以将数组设计为哈希表。

如何操作?首先遍历数组, 对于nums[i],如果它属于[1,n]的范围内, 就将数组中的nums[i]-1的位置进行标记(相当于哈希表记录nums[i]这个值的操作)。操作完成后, 如果所有位置都有标记, 那么答案为n+1, 否则答案就是没有标记的位置的索引+1。

该怎么标记?对于nums[i]∈[1,n] 我们可以将nums[i]-1位置的数转换为负数(这里取相反数), 这样我们就能判断出这个位置是否被标记。由于数组中原本就有些地方有可能存在负数, 我们要把这些负数先变成正数, 而且变成正数的同时不能让它影响到我们对数组中元素的标记, 所以可以统一把它们预处理为nums.length+1。

最后献上代码示例:

public class firstPositiveDeficit {
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1, 2};
        System.out.println(getFirstPositiveDeficit(nums));
    }
    public static int getFirstPositiveDeficit(int[] nums) {
        // 预处理, 将数组中的负数统一转化为n+1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }
        // 标记:
        for (int i = 0; i < nums.length; i++) {
            int x = Math.abs(nums[i]);
            if (x <= nums.length) {
                nums[x - 1] = -Math.abs(nums[x - 1]);
            }
        }
        // 找到第一个没有打上标记的元素的索引, 就是缺失的第一个正数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}