[LeetCode 41] First Missing Positive

作者 Shilei Tian 日期 2017-04-05
[LeetCode 41] First Missing Positive

题目要求

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in $O(n)$ time and uses constant space.

解题思路

这道题目要求用 $O(n)​$ 的时间复杂度和常量的空间来完成,因此开标记数组这种思路肯定就不能用了。之前有一道题目,是利用数组本身来进行计数,可以参见这里,这道题目的空间复杂度要求,肯定也得借鉴利用数组本身这种思路。但是如何借鉴呢?假设我们数组的大小为 n,那么:在不缺失任何元素的情况下,该数组能够存储的最大的数字为 n,即 [1, 2,…, n],那么第一个缺失的正整数肯定就是 n+1。所以,一旦该数组中包含一个大于 n 的数字,那第一个缺失的正整数肯定在 [1, n] 区间内。所以,我们考虑可以将不大于 n 的元素放到其相应的位置,如