Topic link

The following solutions have been submitted for approval.

Solution one, based on a hash table

func firstMissingPositive(nums []int) int {
    l := len(nums)
    if l == 0 {
        return 1
    }
    m := make(map[int]struct{}, l)
    for _, n := range nums {
        m[n] = struct{}{}
    }
    // Map records existing numbers
    for i := 1; i <= l; i++ { [1,l]
        if_, ok := m[i]; ! ok {return i
        }
    }
    return l+1
}
Copy the code

Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).

Solution two, based on counting sort

There is no need to record how many times each positive integer occurs. The solution is essentially the same as the one based on a hash table.

func firstMissingPositive(nums []int) int {
    l := len(nums)
    if l == 0 {
        return 1
    }
    ns := make([]int, l+1) // perform statistics on index [1,l]
    for _, n := range nums {
        if n >= 1 && n <= l { // If the integer [1,l] exists
            ns[n] = 1 // Record the existence of a positive integer. Just record that it appears.}}for i := 1; i <= l; i++ { // iterate over index [1,l], equivalent to iterate over positive integers [1,l]
        if ns[i] == 0 { // Whichever is 0, it does not exist
            return i
        }
    }
    return l+1 // The bottom of the line
}
Copy the code

Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).

Solution three, in place

The solution modifies the input array and requires no additional storage.

func firstMissingPositive(nums []int) int {
    l := len(nums)
    if l == 0 {
        return 1
    }
    for i := 0; i < l; {
        ni := nums[i]
        j := ni- 1 // The target position of ni, such as the integer 1 in index 0 and integer 2 in index 1.
        // ni >= 1&&ni <= l limits the array to be processed and makes j a valid index.
        // i ! = j means that Ni is not in its target position.
        // ni ! = nums[j] If the value equal to ni is already on the index where it should be, no exchange is done.
        if ni >= 1&& ni <= l && i ! = j && ni ! = nums[j] { nums[i], nums[j] = nums[j], ni }else {
            i++
        }
    }
    for i, n := range nums {
        ifi ! = n- 1 {
            return i+1}}return l+1
}
Copy the code

Each element of the array moves at most once to reach its final position, so the time is O(n)O(n)O(n). Based on in-place switching, the space complexity is O(1)O(1)O(1).