First Missing Positive

Question

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

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

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

Thoughts

not O(n)

如果不要求O(n)的话，我们可以先sort然后再找

O(n)

yuanbin

常见的能达到线性时间复杂度的排序算法有 基数排序，计数排序 和 桶排序。

基数排序显然不太适合这道题，计数排序对元素落在一定区间且重复值较多的情况十分有效，且需要额外的 O(n)O(n) 空间，对这道题不太合适。最后就只剩下桶排序了，桶排序通常需要按照一定规则将值放入桶中，一般需要额外的 O(n)O(n) 空间，咋看一下似乎不太适合在这道题中使用，但是若能设定一定的规则原地交换原数组的值呢？这道题的难点就在于这种规则的设定。

设想我们对给定数组使用桶排序的思想排序，第一个桶放1，第二个桶放2，如果找不到相应的数，则相应的桶的值不变(可能为负值，也可能为其他值)。

那么怎么才能做到原地排序呢？即若 A[i] = xA[i]=x, 则将 x 放到它该去的地方 - A[x - 1] = xA[x−1]=x, 同时将原来 A[x - 1]A[x−1] 地方的值交换给 A[i]A[i].

排好序后遍历桶，如果不满足 f[i] = i + 1f[i]=i+1, 那么警察叔叔就是它了！如果都满足条件怎么办？那就返回给定数组大小再加1呗。

Solution

class Solution:
    # @param A, a list of integers
    # @return an integer
    def firstMissingPositive(self, A):
        # write your code here
        if not A:
            return 1
        length = len(A)
        index = 0
        while index < length:
            if A[index] <= 0:
                index += 1
            else:
                if A[index] <= length:
                    if A[index] == A[A[index] - 1] or A[index] == index + 1:
                        #take care of the situation that should move on
                        index += 1
                        continue
                    tmp = A[A[index]-1]
                    A[A[index]-1] = A[index]
                    A[index] = tmp
                    #doesn't increase the index here
                else:
                    index += 1
        for i in range(length):
            if A[i] != i+1:
                return i+1
        #if not return yet, the missing positive number would be length + 1
        return length + 1