缺失的第一个正数

1. 题目描述

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

2. 思路

3. 实现

3.1. HashMap

func firstMissingPositive(nums []int) int {
    m := make(map[int]bool, 0)
    for _, num := range nums {
        m[num] = true
    }

    for i := 1; i <= len(nums);i++ {
        if !m[i] {return i}
    }

    return len(nums)+1
}

3.2. 排序+二分

func firstMissingPositive(nums []int) int {
    sort.Ints(nums)
    for i := 1; i <= len(nums);i++ {
        if binarySearch(nums, i) == -1 {return i}
    }

    return len(nums)+1
}

func binarySearch(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right {
        mid := left + (right-left)>>1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    return -1
}

3.3. 原地Hash

func firstMissingPositive(nums []int) int {
    for i := range nums {
        //维护nums[i]在nums[i]-1的位置这个原地Hash特性
        // 这里用for的原因是[3,4,-1,1]这个用例，交换之后1会遍历不到，没法放到正确的位置
        for {
            val := nums[i]
            index := indexFor(val)
            if index < 0 || index > len(nums)-1 {
                break
            }
            if nums[index] == val{
                break
            }
            nums[i], nums[index] = nums[index], nums[i]
        }

    }
    
    for val := 1; val <= len(nums);val++ {
        index := indexFor(val)
        if nums[index] != val {
            return val
        }
    }
    return len(nums)+1
}

// 类似于自定义Hash映射的index
func indexFor(val int) int {
    // 由于下标的范围是[0,n-1]，而值的范围是[1,n]，所以这里映射到val-1
    return val-1
}

4. 参考

• 原地哈希（哈希函数为：f(nums[i]) = nums[i] - 1） - 缺失的第一个正数 - 力扣（LeetCode）