41. First Missing Positive

Loading...LeetCode

题目follow-up要求O(n)解决，那肯定是需要借助什么规律去缩小结果的范围到n级别。这个 missing positive 肯定小于等于n+1，极限情况下 nums 内是从1到n的整数，那么结果就是n+1，其他任何情况，结果都会是小于n+1的正整数。

暴力解法就是对1到n+1依序做判断，遇到不存在的直接返回，但不是很确定python里if i in nums 这个操作的时间复杂度。

Here is the summary for in:

• list - Average: O(n)

• set/dict - Average: O(1), Worst: O(n)

01/11/2021 Update:

常规sort肯定做不到O(n)，但可以借鉴桶排序bucket sort的思路，给定数组长度为n，那就设置n个桶，对应[1-n] ，给定数组的每个元素都该放到自己对应位置的桶里去，没有合适位置（负数或大于n）就不用管，这样的话，第一个不符合 f[i] = i+1 的数字就是最小的 missing positive.

Brute Force

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if nums == []: 
            return 1
        for i in range(1, max(nums)+2):
            if i not in nums:
                return i
        return 1

Bucket Sort Variant

class Solution:
    def firstMissingPositive(self, A: List[int]) -> int:
        n = len(A)
        # Put every element in the "right" position
        for i in range(n):
            # condition 1: A[i] has its "right" position in the array
            # condition 2: A[i] isn't in its "right" position now
            # condition 3: swap between A[i] and A[A[i]-1] won't be trapped in endless loop -> they are different
            while (0 < A[i] < n) and (A[i] != i+1) and (A[i] != A[A[i]-1]):
                A[A[i]-1], A[i] =  A[i], A[A[i]-1]
                
        # Return the first position with wrong value
        for j in range(n):
            if A[j] != j+1:
                return j+1
            
        # Else, return the total length add 1
        return n+1