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.

解题方法

要达到O(n)的时间复杂度，肯定就不能先把array sort一下了。

而在O(n)的sort方法中有

• radix sort (不适合)
• bucket sort
• counting sort

而counting sort和bucket sort理论上都需要O(n)的space

如果转换思路的话，其实可以将原array当做bucket：

• 因为是找first missing positive, 那么不可能大于array的长度
• 如果value是i, 就放到nums[i-1]中去，这里可以做in-place swap
• 然后再从头遍历，发现第一个nums[i-1] != i的，就是first missing positive

Solution

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1

        length = len(nums)
        i = 0
        while i < length:
            if nums[i] <= 0:
                i += 1
            else:
                if nums[i] <= length:
                    if nums[i] == i+1 or nums[nums[i]-1] == nums[i]:
                        # no need to swap
                        i += 1
                        continue
                    tmp = nums[nums[i]-1]
                    nums[nums[i]-1] = nums[i]
                    nums[i] = tmp
                else:
                    i += 1

        i = 0
        while i < length:
            if nums[i] != i + 1:
                return i + 1
            i += 1

        return length + 1  # no missing until length

Reference