leetcode_41

Golang:

思路：这里补充个并查集实现，时间复杂度也是O(n)，但空间复杂度会差很多，因为使用了哈希表。这题我陷入了个误区，忘记了使用题目给的数组空间是可以算作O(1)的，做的时候还在想，不用额外的空间，怎么可能呢？

代码如下：

func firstMissingPositive(nums []int) int {
    mp:=make(map[int]int)
    for i:=0;i<len(nums);i++{
        if nums[i]>0{
            if mp[nums[i]]==0{
                temp:=mp[nums[i]-1]+mp[nums[i]+1]+1
                mp[nums[i]-mp[nums[i]-1]],mp[nums[i]+mp[nums[i]+1]],mp[nums[i]]=temp,temp,temp
            }
        }
    }
    return 1+mp[1]
}

有疑问加站长微信联系（非本文作者）