41.first-missing-positive.md

41. First Missing Positive

找到最小的缺失正整數，比較直覺的方式是先把所有 nums 中的數字放入 hash map， 之後從 hash map 中找最小的缺失正整數，但是這樣的方法就需要建立一個新的 hash map 所以空間複雜度上並不滿足 O(1)。

Time complexity is O(n), Space complexity is O(n).

Hash map solution:

func firstMissingPositive(nums []int) int {
	hash := map[int]bool{}
	for _, val := range nums {
		hash[val] = true
	}
	var i int = 1
	for true {
		ok, _ := hash[i]
		if !ok {
			return i
		}
		i++
	}
	return -1
}

---

如果想要把 Space complexity O(1) 為目標，可以思考的方向是怎麼把 value 變成在同等大小的 index 下可以作為 hash key 來操作。