41. 缺失的第一个正数 （原地哈希-抽屉原理）

LeetCode: 41. 缺失的第一个正数

相应的类似题目还有：

博客指路：

442. 数组中重复的数据 （ 抽屉原理 ）

448. 找到所有数组中消失的数字（ 抽屉原理 ）

1. 哈希表 （ 从 1 到 n + 1 遍历，查看 哈希表中是否存在， 不存在直接返回即可
2. 二分查找 （ 排序 logn 、之后从 1 到 n 遍历查找，找不到直接返回
3. 优化的二分查找 （ 排序 logn、之后遍历数组， 找到第一个突变的数 >> 即 a r r [ i ] > = 0 arr[i] >= 0 arr[i]>=0 && a r r [ i ] − a r r [ i − 1 ] > 1 arr[i] - arr[i - 1] > 1 arr[i]−arr[i−1]>1
4. 原地哈希 （ 抽屉原理 ） >> 将存在的数 放入到对应的数组下标处， 遍历数组查找数组中值大于0的第一个值 不等于 下标加一 的数返回即可.

原地哈希（抽屉原理）

func firstMissingPositive(nums []int) int {
    len := len(nums)
    // 放置到正确的位置上
    for i, _ := range nums{
        // 比之前的多加了条件
        for nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]{
            swap(nums, nums[i] - 1, i)
        }
    }

    for i, val := range nums{
        if i != val - 1{
            return i + 1
        }
    }

    return len + 1
}

func swap(arr []int, a int, b int){
    if a == b { return  }
    arr[a] = arr[a] ^ arr[b]
    arr[b] = arr[a] ^ arr[b]
    arr[a] = arr[a] ^ arr[b]
}