0041. First Missing Positive | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0041.First-Missing-Positive/

[goalbased]

這樣是不符合 " constant extra space."

[halfrost]

這樣是不符合 " constant extra space."

@goalbased 我这里的 map 是恒定的空间呀。

[goalbased]

map是O(n)，不是O(1)，如果是O(n)的話，我想這題應該放在EASY，我一開始解法跟你一樣的，參考了其他人的解法才發現的，當然也可能是我誤解題目意思了。

[halfrost]

map是O(n)，不是O(1)，如果是O(n)的話，我想這題應該放在EASY，我一開始解法跟你一樣的，參考了其他人的解法才發現的，當然也可能是我誤解題目意思了。

@goalbased 🙏🏻 明白了。我误解了 "constant extra space"，"constant extra space" 指的是不使用额外的空间。我再想想不使用额外空间怎么解答。

[Moonzi-594]

func firstMissingPositive(nums []int) int {
	// 数组长度为n，答案可能的取值为[1, n+1]
	// 原地哈希：index-i => number-i+1
	n := len(nums)
	for i := 0; i < n; i++ {
		for 1 <= nums[i] && nums[i] <= n && nums[i] != nums[nums[i]-1] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}

	for i := 0; i < n; i++ {
		if i+1 != nums[i] {
			return i + 1
		}
	}
	return n + 1
}