Keshawn_lu's Blog

Leetcode 41. 缺失的第一个正数

字数统计: 458阅读时长: 2 min
2020/06/27 Share

题目简介:

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

示例 1:

1
2
输入: [1,2,0]
输出: 3

示例 2:

1
2
输入: [3,4,-1,1]
输出: 2

示例 3:

1
2
输入: [7,8,9,11,12]
输出: 1

提示:

你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间。

思路:

由于时间复杂度为O(n),空间复杂度为O(1),所以不能使用简单的哈希表或排序等方法。

所以我们使用置换的方法,在遍历数组时,将nums[i]放置到nums[nums[i] - 1]的位置上,比如nums[i] = 3就放置到nums[2],即nums[2] = 3

这样子最后的结果数组便为[1,2,3,4,...,nums.size()]。只要nums[i] != i + 1,那么这个数就是缺失的数,返回即可。

在置换时需要考虑以下几点:

  1. 首先0 < nums[i] <= nums.size(),也就是1 ~ nums.size()的范围,才可以进行置换。
  2. nums[i] == nums[nums[i] - 1],即该位置上已放置了正确的数字,那么不必再置换,否则会造成死循环,一直置换下去。

代码如下:

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
32
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {

for(int i = 0; i < nums.size(); i++){

while(nums[i] != i + 1){ //不为正确的数字

//不在1 ~ nums.size()范围内
if(nums[i] <= 0 || nums[i] > nums.size())
break;
//num[nums[i] - 1]位置上已经放置了正确的数字,不必再交换,否则会是死循环
if(nums[i] == nums[nums[i] - 1])
break;

//交换,使nums[i]放置到正确位置
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp; //新的nums[i]
}
}

for(int i = 0; i < nums.size(); i++){

if(nums[i] != i + 1)
return i + 1;
}

return nums.size() + 1;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: