给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

思路

  1. 可能存在的题解为 1 ~ n + 1
  2. 可将 nums 原地调整，将 1 ~ n 的数值存放到各自下标中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var firstMissingPositive = function (nums) {
  const n = nums.length
  nums.push(nums[0])
  nums[0] = 0
  for (let i = 1; i <= n; ++i) {
    let val = nums[i]
    while (i !== val && val > 0 && val <= n && val !== nums[val]) {
      ;[nums[i], nums[val]] = [nums[val], nums[i]]
      val = nums[i]
    }
  }
  let result = 1
  for (let i = 1; i <= n; ++i) {
    if (nums[i] !== i) {
      break
    }
    ++result
  }
  return result
}