每天一道leetcode(Day 47)

41. 缺失的第一个正数

题目描述

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

示例

• 示例  1:

输入: [1,2,0]
输出: 3

• 示例  2:

输入: [3,4,-1,1]
输出: 2

• 示例  3:

输入: [7,8,9,11,12]
输出: 1

提示：

你的算法的时间复杂度应为 O(n)，并且只能使用常数级别的额外空间。

解题思路

• 解题思路：计数排序-原地交换版

• 其实原地交换，只是借助本身数组进行交换扩张

  • 如果 num[i] != nums[nums[i]]，说明需要像经典版那样以值 num[i]为索引 计数放入原数组，而因为原数组索引 nums[i] 处的值 nums[nums[i]] 可能有值，为了不漏掉，就需要交换

  • 重复上面交换动作，直至 nums[i] <= 0

注意：如果需要对原数组排序，这仅仅适用于原数组没有重复元素的情况。因为如果有重复元素，你不知道 nums[nums[i]]处的值是 nums[i]替换过来的，还是本身也等于这个数但此题仅仅需要找寻缺失的第一个正数，因此重复的没有关系，只记录一次就好，不需要排序，所以就不用管重复的元素，直接跳过即可。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  let n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] >= 0 && nums[i] <= n && nums[nums[i]] !== nums[i]) {
      [nums[nums[i]], nums[i]] = [nums[i], nums[nums[i]]];
    }
  }
  for (let i = 0; i <= n; i++) {
    if (nums[i] !== i) {
      if (i > 0) return i;
    }
  }
  return n + 1;
};

参考

41. 缺失的第一个正数