First Missing Positive

Date:

　　Nov. 1, 2017

Problem:

　　https://leetcode.com/problems/first-missing-positive/description/

Description:

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

　　For example,

Give [1, 2, 0], return 3
Give [3, 4, -1, 1] return 2

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

　　

　　emmmmmm。

　　我有一个大胆的想法。

class Solution:
    def firstMissingPositive(self, nums):
        pst = list(range(2333333))
        for i in nums:
            if i > 0:
                pst[i] = 0
        for i in pst:
            if i > 0:
                return i

　　本地测试，代码运行时间在200~300ms间。

　　提交，TLE。

　　一看数据，[1, 1, 1, 1, 1]，不对劲呀。本地一跑，300ms，没问题。再提交，TLE。

　　认真看了看数据，发现前面已经过了一半测试点，不可能在这地方栽了。目测是反复运行同一函数累计时间超时了（和codewars一个尿性）。

class Solution:
    def firstMissingPositive(self, nums):
        pst = list(range(23333))
        for i in nums:
            if i > 0:
                pst[i] = 0
        for i in pst:
            if i > 0:
                return i

　　提交，AC。

　　……

　　2333333。

　　正经的解法。

　　中心思想其实和计数排序有点像：把数放到它们该去的地方。

　　考虑一个长度为k的输入，它最多无死角覆盖1~k这些正整数，如果有大于k的数，1~k中显然会出现我们要找的missing positive。所以我们要做的事情就是将nums[1]~nums[k]放回它们该待的地方——如果放得进去的话（它们必须不能是负数或者超过k的数）。而当它们确实都覆盖了1~k时，我们要找的数就是k+1。

　　另一个更好理解的角度，k+1个抽屉，k个苹果，容斥原理。

　　所以我们令i=0~(k-1)，检查每一个nums[i]，当nums[i]在1到k之间（有位可放），nums[i] != nums[nums[i]-1]（还没放入）时，我们就将nums[i]与nums[nums[i]-1]交换，将正确的数放入，不正确的数取出，不断重复此操作，直到发现nums[i]是无位可放的为止。

　　在操作过一遍之后，我们再度检查nums[i]，返回第一个nums[i] != i+1（不正确）的数i+1。如果没有检查到，就返回k+1。

　　这个算法的复杂度为O(N)。

　　以下是submission。

class Solution:
    def firstMissingPositive(self, nums):
        k = len(nums)
        for i in range(k):
            while 0 < nums[i] <= k and nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(k):
            if nums[i] != i + 1:
                return i + 1
        return k + 1