[force buckle]41 Missing first positive number

Consistent with the topic AC Code

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while nums[i] != i + 1 and nums[i] > 0 and nums[i] < n and nums[i] != nums[nums[i] - 1]:
                #nums[i],nums[nums[i] - 1] = nums[nums[i] - 1],nums[i]
                t1,t2 =nums[i],nums[nums[i] - 1]
                nums[nums[i] - 1] = t1
                nums[i] = t2

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

Not in line with the title AC Code

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        D = {
    }
        for it in nums:D[it] = 1
        i = 1
        while i in D.keys(): i += 1
        return i

analysis

Because the time complexity of this problem is $O(n)$, And the value range of the element is the integer range , So the easiest way to think of is to use hash table —— With the help of hash table, mark every value that appears , The hash time of each value is $O(1)$, The total complexity of hash is $O(n)$. And then from 1 Start to find the first integer that does not appear in the hash table , The expected time complexity of the traversal process is $O(n/2)$. So the total time complexity of this process is $O(n)$, Meet the requirements of the topic . However , The problem also has strict requirements for the spatial complexity of the algorithm ——$O(1)$ Time complexity of .
The spatial complexity of using hash tables is linear , Obviously does not meet the requirements of the topic .

For this question , Use hash table What a beautiful thing , But the space complexity of hash table is not up to standard , What are the optimization strategies ？

Here we need to use some characteristics of the data itself .
That is to build a special hash table with the help of the particularity of the data itself , achieve $O(1)$ Complexity requirements .

As shown in the figure , We can put each number where it should be , The final result we use $O(n)$ The complexity of completes the mapping of numeric values and array subscripts —— That is hash .

It should be noted that , The value of the number in the array may be negative 、 It may also be a large number .
For these numbers , We can ignore —— Because the array length is only n, So the first positive number missing cannot be greater than n + 1.

Are we using $O(n)$ The time complexity of sorting an array ？
Yes .
According to conventional cognition , Sort an array , The most time complexity is $O(nlo{g}_{2}n)$, Why can it be achieved here $O(n)$ What about the order of ？

That's because we take advantage of the particularity of this array —— Or the particularity of sorting rules —— We only sort the data within a limited range of integers , And each number should not be repeated when sorting （ Otherwise, the number will be ignored ）.

---

Topic link
Originality is not easy. , Thank you for your support ！