LeetCode.41缺失的第一个正数详解

问题描述

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

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

关键概念

解决这个问题需要理解以下几个关键概念：

1. 原地哈希

原地哈希是一种使用数组本身作为哈希表来存储信息的技术，不需要额外的存储空间。这种方法通过修改数组中的元素来标记信息，从而避免了额外的空间复杂度。

2. 索引与值的映射

在这个问题中，我们利用数组的索引来代表正整数值。通过确保所有的正整数均在数组中有一个对应的索引，我们可以通过索引位置来判断一个数是否存在于数组中。

解题思路1

步骤 1: 数据清洗

首先，我们需要遍历数组，将所有非正整数以及大于数组长度的数替换为一个大于数组长度的值（例如 n+1）。这样做的目的是确保数组中只包含与索引有关的有效正整数。

步骤 2: 利用数组标记正整数的存在

再次遍历数组，对于每个数 x（满足 1 <= x <= n），将位置 x-1 的元素标记为负数。这个操作是利用原地哈希的核心，通过标记来记录一个数字的存在。

步骤 3: 寻找最小的未标记索引

最后，遍历数组查找第一个非负数的索引，该索引加 1 即为未出现的最小正整数。如果所有位置均已标记为负数，则数组包含从 1 到 n 的所有整数，因此缺失的最小正整数是 n+1。

复杂度分析

• 时间复杂度：O(n)。整个解决方案涉及对数组的几次遍历，每次遍历的复杂度为 O(n)。
• 空间复杂度：O(1)。由于使用了原地哈希，除了输入数组外没有使用任何额外的空间。

代码实现

#include <iostream>
#include <vector>
 
using namespace std;
 
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
 
    // 步骤1: 将所有非正数和大于n的数替换为n+1
    for (int i = 0; i < n; ++i) {
        if (nums[i] <= 0 || nums[i] > n) {
            nums[i] = n + 1;
        }
    }
 
    // 步骤2: 利用数组本身作为哈希表来标记数组中存在的数
    for (int i = 0; i < n; ++i) {
        int num = abs(nums[i]);
        if (num > n) {
            continue; // 跳过因为它不是有效的索引
        }
        num--; // 将数值转换为索引
        if (nums[num] > 0) { // 如果未标记，则标记为负数
            nums[num] = -nums[num];
        }
    }
 
    // 步骤3: 寻找第一个未被标记的位置
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 0) {
            return i + 1; // 返回缺失的最小正整数
        }
    }
 
    return n + 1; // 如果数组完整包含了从1到n的整数，则返回n+1
}
 
int main() {
    vector<int> nums = {3, 4, -1, 1};
    cout << "缺失的最小正整数是 " << firstMissingPositive(nums) << endl;
    return 0;
}

解题思路2

步骤 1: 放置数字到其理想位置

首先，遍历数组，对于每个元素，如果它是一个正整数并且它不在它的理想位置（例如数字 iii 应该位于索引i−1），则将它与其理想位置上的元素交换。这个过程可能需要多次交换才能将一个元素放到正确的位置。这种策略确保了所有在数组范围内的数都放置在正确的位置，如果有的话。

步骤 2: 确定未出现的最小正整数

再次遍历数组，第一个其索引+1不等于其值的位置，就指示了未出现的最小正整数。如果所有的位置都正确，那么未出现的最小正整数就是数组长度+1。

为什么要这样做？

这种放置方式让我们能够在常数时间内，通过直接检查索引位置来确认数字是否存在。比如，如果我们想知道数字 3 是否在数组中，我们只需要检查索引 2 的位置即可。

代码实现

#include <iostream>
#include <vector>
 
using namespace std;
 
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[nums[i] - 1], nums[i]);
        }
    }
 
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
 
    return n + 1;
}
 
int main() {
    vector<int> nums = {3, 4, -1, 1};
    cout << "缺失的最小正整数是 " << firstMissingPositive(nums) << endl;
    return 0;
}