题解

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

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

Leetcode 17.缺失的第一个正数-原题链接

题目描述

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

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

输入格式

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

输出格式

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

输入样例1

3
1 2 0

输出样例1

3

样例说明

范围 [1,2] 中的数字都在数组中。

输入样例2

4
3 4 -1 1

输出样例2

2

输入样例3

5
7 8 9 11 12

输出样例3

1

数据范围

1 <= nums.length <= 10^5 -2^31 <= nums[i] <= 2^31 - 1