题目链接
英文链接:https://leetcode.com/problems/first-missing-positive/
中文链接:https://leetcode-cn.com/problems/first-missing-positive/
题目详述
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
示例 1:
1 | 输入: [1,2,0] |
示例 2:
1 | 输入: [3,4,-1,1] |
示例 3:
1 | 输入: [7,8,9,11,12] |
说明:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
题目详解
- 借用桶排序的思想,一个萝卜一个坑。每次把
[1, n]
上的数放到对应的位置上,第一个出现空缺的位置就是缺失的第一个正数。 - 易知结果范围为
[1, n + 1]
,其中n + 1
可以特判出来。我们只用关心数组中处于区间[1, n]
的数。 - 遍历数组,如果当前元素不处于区间
[1, n]
,跳过当前元素;否则把交换当前元素到正确的位置,并继续此操作,直到当前元素不处于区间[1, n]
或者当前元素已经在正确的位置。 - 最后遍历一次数组,如果发现当前元素不等于它的下标加一,直接返回下标加一(下标 0 存储 1, 下标 1 存储 2……)。
- 如果前面没有返回。说明
[1, n]
的数都存在,缺失的第一个正数为n + 1
。
1 | public class LeetCode_00041 { |