题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
解法
方法一：原地交换
我们假设数组 $nums$ 长度为 $n$，那么最小的正整数一定在 $[1, .., n + 1]$ 之间。我们可以遍历数组，将数组中的每个数 $x$ 交换到它应该在的位置上，即 $x$ 应该在的位置为 $x - 1$。如果 $x$ 不在 $[1, n + 1]$ 之间，那么我们就不用管它。
遍历结束后，我们再遍历数组，如果 $i+1$ 不等于 $nums[i]$，那么 $i+1$ 就是我们要找的最小的正整数。
时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
def swap(i, j):
nums[i], nums[j] = nums[j], nums[i]
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
swap(i, nums[i] - 1)
for i in range(n):
if i + 1 != nums[i]:
return i + 1
return n + 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; ++i) {
if (i + 1 != nums[i]) {
return i + 1;
}
}
return n + 1;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (i + 1 != nums[i]) {
return i + 1;
}
}
return n + 1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func firstMissingPositive(nums []int) int {
n := len(nums)
for i := range nums {
for nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
for i, v := range nums {
if i+1 != v {
return i + 1
}
}
return n + 1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | function firstMissingPositive(nums: number[]): number {
const n = nums.length;
let i = 0;
while (i < n) {
const j = nums[i] - 1;
if (j === i || j < 0 || j >= n || nums[i] === nums[j]) {
i++;
} else {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
const res = nums.findIndex((v, i) => v !== i + 1);
return (res === -1 ? n : res) + 1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | impl Solution {
pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut i = 0;
while i < n {
let j = nums[i] - 1;
if (i as i32) == j || j < 0 || j >= (n as i32) || nums[i] == nums[j as usize] {
i += 1;
} else {
nums.swap(i, j as usize);
}
}
(nums
.iter()
.enumerate()
.position(|(i, &v)| (v as usize) != i + 1)
.unwrap_or(n) as i32)
+ 1
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | public class Solution {
public int FirstMissingPositive(int[] nums) {
int n = nums.Length;
for (int i = 0; i < n; ++i) {
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
Swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < n; ++i) {
if (i + 1 != nums[i]) {
return i + 1;
}
}
return n + 1;
}
private void Swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | int firstMissingPositive(int* nums, int numsSize) {
for (int i = 0; i < numsSize; ++i) {
while (nums[i] >= 1 && nums[i] <= numsSize && nums[i] != nums[nums[i] - 1]) {
swap(&nums[i], &nums[nums[i] - 1]);
}
}
for (int i = 0; i < numsSize; ++i) {
if (i + 1 != nums[i]) {
return i + 1;
}
}
return numsSize + 1;
}
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
/**
* @param integer[] $nums
* @return integer
*/
function firstMissingPositive($nums) {
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] <= 0) {
$nums[$i] = $n + 1;
}
}
for ($i = 0; $i < $n; $i++) {
$num = abs($nums[$i]);
if ($num <= $n) {
$nums[$num - 1] = -abs($nums[$num - 1]);
}
}
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] > 0) {
return $i + 1;
}
}
return $n + 1;
}
}
|