题解

本题要求 时间复杂度 O(n) 且 常数级额外空间。常见方法包括：

• 哈希表：O(n) 时间，但空间 O(n)，不符合要求。
• 排序：O(n log n)，不符合要求。
• "原地置换" 方法：符合要求，利用数组本身作为哈希表。

解法：原地交换（符合 O(n) 时间 & O(1) 空间）

思路

1. 遍历数组，将 nums[i] 放到正确的位置 nums[i] - 1（即 1 应该在索引 0，2 应该在 1）。
2. 遍历一次数组，找到第一个 nums[i] != i + 1 的位置，返回 i + 1 作为答案。

步骤

• 对于

  nums[i]
  

  ：

  • 若 1 <= nums[i] <= n 且 nums[i] != nums[nums[i] - 1]，则交换 nums[i] 和 nums[nums[i] - 1]。
  • 直到无法交换为止。

• 遍历数组，若 nums[i] != i + 1，则返回 i + 1。

• 若所有 1~n 均正确，则返回 n + 1。

时间 & 空间复杂度

• 时间复杂度：每个元素最多移动 两次，所以是 O(n)。
• 空间复杂度：O(1)（只使用了常数级变量）。

代码实现

C++ 实现

#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[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }

    // 找到第一个 nums[i] != i + 1
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    
    return n + 1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    cout << firstMissingPositive(nums) << endl;
    return 0;
}

Python 实现

def first_missing_positive(nums):
    """
    找到数组中缺失的最小正整数
    """
    n = len(nums)
    
    # 置换到正确位置
    for i in range(n):
        while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

    # 找到第一个 nums[i] != i + 1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    print(first_missing_positive(nums))

Java 实现

import java.util.Scanner;

public class Main {
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 置换到正确位置
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        // 找到第一个 nums[i] != i + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        scanner.close();

        System.out.println(firstMissingPositive(nums));
    }
}

题目描述

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

输入格式

• 第一行输入整数 n，表示数组 nums 的长度。
• 第二行输入 n 个整数，表示数组 nums 的元素。

输出格式

• 输出一个整数，表示 nums 中缺失的最小正整数。

输入样例

3
1 2 0

输出样例

3