First Missing Positive Number
给出一个无序的正数数组,找出其中没有出现的最小正整数。
样例
如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2
挑战
只允许时间复杂度O(n)的算法,并且只能使用常数级别的空间。
Solution
容易想到的方案是先排序,然后遍历求得缺的最小整数。排序算法中常用的基于比较的方法时间复杂度的理论下界为 O(nlogn), 不符题目要求。常见的能达到线性时间复杂度的排序算法有 基数排序,计数排序 和 桶排序。
基数排序显然不太适合这道题,计数排序对元素落在一定区间且重复值较多的情况十分有效,且需要额外的 O(n) 空间,对这道题不太合适。最后就只剩下桶排序了,桶排序通常需要按照一定规则将值放入桶中,一般需要额外的 O(n) 空间,咋看一下似乎不太适合在这道题中使用,但是若能设定一定的规则原地交换原数组的值呢?这道题的难点就在于这种规则的设定。
设想我们对给定数组使用桶排序的思想排序,第一个桶放1,第二个桶放2,如果找不到相应的数,则相应的桶的值不变(可能为负值,也可能为其他值)。
那么怎么才能做到原地排序呢?即若 A[i]=x, 则将 x 放到它该去的地方 - A[x−1]=x, 同时将原来 A[x−1] 地方的值交换给 A[i].
排好序后遍历桶,如果不满足 f[i]=i+1, 那么警察叔叔就是它了!如果都满足条件怎么办?那就返回给定数组大小再加1呗。
Complexity
时间复杂度 O(n),空间复杂度 O(n)
public class Solution {
/**
* @param A: an array of integers
* @return: an integer
*/
public int firstMissingPositive(int[] A) {
int size = A.length;
for (int i = 0; i < size; ++i) {
while (A[i] > 0 && A[i] <= size &&
(A[i] != i + 1) && (A[i] != A[A[i] - 1])) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
}
}
for (int i = 0; i < size; ++i) {
if (A[i] != i + 1) {
return i + 1;
}
}
return size + 1;
}
}
核心代码为那几行交换,但是要很好地处理各种边界条件则要下一番功夫了,要能正常的交换,需满足以下几个条件:
- A[i] 为正数,负数和零都无法在桶中找到生存空间...
- A[i] <= size 当前索引处的值不能比原数组容量大,大了的话也没用啊,肯定不是缺的第一个正数。
- A[i] != i + 1, 都满足条件了还交换个毛线,交换也是自身的值。
- A[i] != A[A[i] - 1], 避免欲交换的值和自身相同,否则有重复值时会产生死循环。
如果满足以上四个条件就可以愉快地交换彼此了,使用while循环处理,此时i并不自增,直到将所有满足条件的索引处理完。