LC.P41[缺失的第一个正数]

题目描述

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

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

示例1

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

示例2

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

示例3

输入：nums = [7,8,9,11,12]
输出：1

提示：

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        for (int i = 1; i <= nums.length; ++i) {
            if (!set.contains(i)) return i;
        }
        return nums.length + 1;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：原地哈希

将数组视为哈希表，自定义哈希函数：数值为 i 的数映射到下标为 i - 1 的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    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]) {
                // 数值'1'映射到下标'0'，'2'映射到下标'1',...
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$