给定一个未排序的整数数组 nums，请你找出其中没有出现的 最小的正整数。
n，表示数组 nums 的长度。n 个整数，表示数组 nums 的元素。nums 中缺失的最小正整数。3
1 2 0
3
本题要求 时间复杂度 O(n) 且 常数级额外空间。常见方法包括：
O(n) 时间，但空间 O(n)，不符合要求。O(n log n)，不符合要求。nums[i] 放到正确的位置 nums[i] - 1（即 1 应该在索引 0，2 应该在 1）。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)（只使用了常数级变量）。#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;
}
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))
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));
}
}