41. 缺失的第一个正数

思路

• 题目不让用额外的空间，时间复杂度又要是 O(n)
• 我们可以利用 nums 数组这个空间本身，不影响 nums 数组的原信息的情况下，利用它存储一些额外的信息

缺失的最小正整数的范围

• 假设它为 n，n >= 1 是肯定的，还意味着 1 、2、 3、 …… 、n-1 肯定在数组里存在
• 如果排好序的话，元素 1 ~ n-1 排在数组的前面，然后 n 缺失，比 n 大的元素在不在数组里都不影响 n 是缺失的最小正整数
• 所以 nums 数组的长度最短可以是 n-1，nums.length >= n-1 ，即 n >= nums.length+1
• 比方说，数组有 5 个元素，n 肯定是在 [1,6] 中。n 为 6 ，就是 1~5 正好占满了数组

交换元素 重排数组

• 我们希望数组中尽量小的正整数放在前面，以便更快地找到目标 n
• 1 出现在 位置 0 ，2 出现在位置 1…… 遍历时看哪个位置没有出现该出现的元素
• 即，nums[i] 从 位置 i 交换到 位置 nums[i]-1 。[1,nums.length+1] 以外的数不用交换

题目把 nums 看作一个集合

• 题意把 nums 数组当做一个存放元素的集合，找出没有出现在集合里的最小正整数
• 对元素进行位置的交换，元素继续存在于集合中，没有改变原有的信息
• 将部分的数安排到合适的位置，让 nums 数组承载一些额外信息，帮助解决问题

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    while (
      nums[i] >= 1 &&
      nums[i] <= nums.length && // 对1~nums.length范围内的元素进行安排
      nums[nums[i] - 1] !== nums[i] // 已经出现在理想位置的，就不用交换
    ) {
      const temp = nums[nums[i] - 1] // 交换
      nums[nums[i] - 1] = nums[i]
      nums[i] = temp
    }
  }
  // 现在期待的是 [1,2,3,...]，如果遍历到不是放着该放的元素
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] != i + 1) {
      return i + 1
    }
  }
  return nums.length + 1 // 发现元素 1~nums.length 占满了数组，一个没缺
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  nums = [...new Set(nums)].sort((a, b) => a - b)
  let index = nums.indexOf(1)
  if (index === -1) {
    return 1
  }
  let num = 2
  for (let i = index + 1; i < nums.length; i++, num++) {
    if (nums[i] !== num) {
      break
    }
  }
  return num
}