leetcode41：缺失的第一个正数

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

/*
    所有的数放入哈希表，从 1 开始依次枚举正整数，判断否在哈希表中。
    
    时间复杂度：O(n)
        其中 n 是数组的长度，遍历数组两次。
    空间复杂度：O(n)
*/
class Solution_0 {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> set;
        for (const auto& x : nums) {
            set.insert(x);
        }

        int res = 1;
        while (set.count(res)) {
            res++;
        }

        return res;
    }
};

/*
    置换：将每个数字放在数组中的正确位置，数字 i 应该放在数组的索引 i-1 处。

    第一次遍历数组：
        将每个正数 nums[i] 放置到正确的位置 nums[nums[i]-1]，通过交换元素来实现。
    第二次遍历数组：
        找到第一个不满足 nums[i] != i+1 的位置 i，i+1 即为缺失的第一个正数。
    
    时间复杂度：O(n)
        其中 n 是数组的长度，遍历数组两次。
    空间复杂度：O(1)
*/
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        // 将每个数字放到正确的位置
        for (int i = 0; i < n; i++) {
            // 处理范围 [1, n]，不在正确位置上的数字
            while (nums[i] >= 1 && nums[i] <= n 
                && nums[i] != i+1 && nums[i] != nums[nums[i]-1]) {
                swap(nums[i], nums[nums[i]-1]);
            }
        }
        // 找出第一个不在正确位置上的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }

        // 所有位置都正确，返回 n+1
        return n+1;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,0},
        {3,4,-1,1},
        {7,8,9,11,12},
    };

    for (size_t i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        cout << "Input: ";
        printArray(nums);
        cout << endl;

        int result = solution.firstMissingPositive(nums);
        cout << "Output: " << result << endl;
        // printArray(nums);
        // cout << endl;
    }

    return 0;
}