041-缺失的第一个正数

原题：缺失的第一个正数

思路：把数组本身当成哈希表，把数放回其值对应的下标处，例如值 1 放到 0 下标，没有放合法值的第一个下标 + 1 就是缺失的数

思路

1. 遍历数组，对每个下标，在符合某些条件的情况下，不断把该下标上的元素与其值减一的下标处的元素进行替换
   nums[nums[i] - 1] = nums[i]

2. 替换的条件为:
   该位置上的元素为正整数 且 元素值小于等于数组长度 且 在替换目标下标上的值不等于当前值(Note: 重点)**
   nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]

3. 再次遍历整个数组，找出下标与其值对应不上的下标，该数就是缺失的最小正整数
   nums[i] !== i + 1

4. 如果没找到，说明整个数组是从 1 开始的连续正整数数组，返回数组长度 + 1 即可

1. 遍历数组每个下标，替换目标元素

细节都在思路和注释里，上实现:

for (let i = 0; i < nums.length; i++) {
  // 把当前位置的数放到正确的下标
  // 直到数超出数组边界 或 正确下标上已有正确的数
  while (
    nums[i] > 0 &&
    nums[i] <= nums.length &&
    // 【重点】
    // 当前位置的数不能与其目标下标下的数相同
    // 可以防止陷入两数相同的死循环
    // 同时还能确定目标下标下是否需要替换
    nums[nums[i] - 1] !== nums[i]
  ) {
    // 这里要先记录目的下标，因为会被替换
    const targetIndex = nums[i] - 1;
    const temp = nums[i];
    nums[i] = nums[targetIndex];
    nums[targetIndex] = temp;
  }
}

2. 遍历数组，找到与元素不对应的下标

没啥好说的，直接上实现:

// 遍历判断，不在正确位置上的数的下标 + 1 就是缺失的最小正整数
for (let i = 0; i < nums.length; i++) {
  if (nums[i] !== i + 1) return i + 1;
}
// 如果全部都在位置上，返回数组长度 + 1
return nums.length + 1;

完整代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    // 把当前位置的数放到正确的下标
    // 直到数超出数组边界 或 正确下标上已有正确的数
    while (
      nums[i] > 0 &&
      nums[i] <= nums.length &&
      // 【重点】
      // 当前位置的数不能与其目标下标下的数相同
      // 可以防止陷入两数相同的死循环
      // 同时还能确定目标下标下是否需要替换
      nums[nums[i] - 1] !== nums[i]
    ) {
      // 这里要先记录目的下标，因为会被替换
      const targetIndex = nums[i] - 1;
      const temp = nums[i];
      nums[i] = nums[targetIndex];
      nums[targetIndex] = temp;
    }
  }
  // 遍历判断，不在正确位置上的数的下标 + 1 就是缺失的最小正整数
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  // 如果全部都在位置上，返回数组长度 + 1
  return nums.length + 1;
};