# 41. First Missing Positive

{% embed url="<https://leetcode.com/problems/first-missing-positive/>" %}

题目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.

{% tabs %}
{% tab title="Brute Force" %}

```python
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
```

{% endtab %}

{% tab title="Bucket Sort Variant" %}

```python
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
```

{% endtab %}
{% endtabs %}
