题解 | 缺失的第一个正整数

1、解题思路

哈希表法（不符合空间要求）：使用哈希表记录所有出现的数字。从1开始逐个检查，直到找到第一个不在哈希表中的正整数。时间复杂度：O(n)，空间复杂度：O(n)。
原地哈希法：利用数组本身作为哈希表，将数字 x 放到索引 x-1 的位置。遍历数组，将每个数字放到正确的位置。再次遍历数组，找到第一个 nums[i] != i+1 的位置，返回 i+1。如果所有位置都正确，返回 n+1。时间复杂度：O(n)，空间复杂度：O(1)。
标记法：首先将所有非正数和大于 n 的数标记为无效（例如设为 n+1）。遍历数组，将数字 x 对应的索引 x-1 的位置标记为负数。再次遍历数组，找到第一个正数的位置，返回 i+1。如果所有位置都为负数，返回 n+1。时间复杂度：O(n)，空间复杂度：O(1)。

2、代码实现

C++

#include <fstream>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int minNumberDisappeared(vector<int>& nums) {
        // write code here
        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[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

3、复杂度分析

原地哈希法：通过交换将数字 x 放到索引 x-1 的位置。确保每个数字都在其正确的位置上。再次遍历时，第一个不匹配的位置即为缺失的最小正整数。
效率：时间复杂度：O(n)，尽管有嵌套循环，但每个数字最多被交换一次。空间复杂度：O(1)，仅使用常数额外空间。
边界条件：如果数组包含所有 1 到 n 的数字，则返回 n+1。如果数组为空，返回 1。