算法刷题目数组和矩阵
Source
Edit
History

缺失的第一个正数

一、题目

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

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

Leetcode：https://leetcode.cn/problems/first-missing-positive/description/

二、分析

对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。

我们的流程为：

  • 将数组中所有小于等于 0 的数修改为 N+1。此时数组中的数字都是大于 0 的。
  • 我们遍历数组中的每一个数 x，如果 |x| 在 [1, N] 区间，那么我们给数组中第 |x|-1 个位置的数添加一个负号。如果他已经是负数了，不需要重复添加。还有遍历过程可能会修改数组中元素的正负号，因此判断时要取绝对值。
  • 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        int n = nums.size();
        for (auto& x : nums) {
            if (x <= 0) {
                x = n+1;
            }
        }
        for (int i = 0; i < n; i++) {
            int num = std::abs(nums[i]);
            if (num <= n) {
                nums[num-1] = -std::abs(nums[num-1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }
};

时间复杂度：O(N)，空间复杂度：O(1)