LeetCode 算法：缺失的第一个正数c++

原题链接🔗：缺失的第一个正数
难度：困难⭐️⭐️⭐️

题目

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

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

示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

题解

置换数组法

题解：

“缺失的第一个正数” 是一个常见的算法问题，通常可以通过以下步骤来解决：

问题理解：给定一个未排序的整数数组，其中可能包含负数、零和重复的正数。数组中应该包含从1到n的整数，但有一个正数缺失了。任务是找到并返回这个缺失的正数。

初始化：首先，我们需要一个方法来快速判断数组中是否存在一个特定的正整数。

使用数组索引：我们可以利用数组的索引来帮助我们找到缺失的正数。由于数组索引从0开始，我们可以将数组中的每个正整数移动到它应该在的位置上，即索引i应该包含值i+1。

处理非正数：将所有非正数（包括0和负数）以及大于数组长度的正数放到数组的末尾或忽略它们，因为它们不影响找到缺失的正数。

交换元素：遍历数组，对于每个正整数，如果它不在正确的位置上，就将它与正确的位置上的数交换。重复这个过程，直到所有正整数都位于正确的位置上，或者遇到一个已经在正确位置上的数。

寻找缺失的数：在完成上述步骤后，遍历数组，第一个不在正确位置上的索引i加1就是缺失的正数。

特殊情况处理：如果数组中所有的1到n都在正确的位置上，那么缺失的数就是n+1。

时间复杂度：这个方法的时间复杂度是O(n)，因为每个元素最多被交换一次。

空间复杂度：空间复杂度是O(1)，因为我们只使用了常数级别的额外空间。

通过这种方法，我们可以高效地找到缺失的第一个正数，而不需要对数组进行排序或使用额外的存储空间。这种方法利用了原数组的空间，通过交换元素来减少所需的时间。

复杂度：时间复杂度是O(n，空间复杂度是O(1)
过程：

定义Solution类及其公共成员函数firstMissingPositive。这个函数接收一个整数类型的vector作为参数。

遍历数组nums，将所有非正数或大于数组大小的数设置为0。这是因为这些数值不会影响第一个缺失的正整数。

通过一个循环，将数组中的每个元素映射到它应该在的索引位置。例如，如果数组中有数字1，它应该被放置在索引0的位置。这里使用abs函数来获取元素的绝对值，然后减去1得到索引。接着使用swap函数交换元素，直到元素被放置在正确的位置。

再次遍历数组，寻找第一个其值不等于索引加1的元素。如果找到了这样的元素，那么缺失的正整数就是这个索引加1。

如果数组中的每个元素都与其索引加1相匹配，那么缺失的正整数就是数组大小加1。

main函数中，定义了一个vector<int>类型的数组nums，并初始化了一些元素。然后创建了Solution类的实例，并调用firstMissingPositive函数来找出缺失的第一个正整数，最后输出结果。

程序结束，返回0表示正常退出。

c++ demo：

#include <iostream>
#include <vector>
#include <cstdlib> // 用于abs函数
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        // 将数组中的非正数和大于n的数标记为0，因为它们不会影响第一个缺失的正数
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = 0;
            }
        }

        // 利用原数组空间，将1-n的数字映射到数组的索引上
        for (int i = 0; i < n; ++i) {
            int index = abs(nums[i]) - 1;
            while (index >= 0 && index < n && nums[index] != abs(nums[i])) {
                swap(nums[i], nums[index]);
                index = abs(nums[i]) - 1;
            }
        }

        // 遍历数组，找出第一个索引不匹配的元素，其索引+1即为缺失的正数
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 如果所有位置都匹配，那么缺失的正数是n+1
        return n + 1;
    }
};

int main() {
    vector<int> nums = { 3, 4, -1, 1 };
    Solution solution;
    cout << "The first missing positive is: " << solution.firstMissingPositive(nums) << endl;
    return 0;
}