41.H 缺失的第一个正数

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

思路

如果不考虑空间复杂度，用一个map来存储哪些正数已经存在过，然后再从1开始逐个检查是最简单的思路。

在有空间复杂度要求的情况下，可以考虑通过更改原数组的方式来记录每个整数是否存在。主要步骤：

1. 先把无关的数字排除，标记为n+1

2. 遍历数组，如果当前位置的绝对值abs(num)小于等于n，那么将位置num-1的元素改为负数。此处需要注意已经改为负数的情况。

3. 遍历数组，发现第一个大于0的数字后，返回当前数字的下标+1。大于0说明当前索引位置对应的数字不存在。

Code

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i, num := range nums {
		// 此处应该包含等于的情况，0也属于无关数字
		if num <= 0 {
			nums[i] = n + 1
		}
	}

	for _, num := range nums {
		num = abs(num)
		// 注意此处应该包含等于的情况
		if num <= n {
			nums[num-1] = -abs(nums[num-1])
		}
	}

	for i, num := range nums {
		if num > 0 {
			return i + 1
		}
	}

	return n + 1
}

func abs(num int) int {
	if num < 0 {
		return -num
	}

	return num
}