41.缺失的第一个正数

链接：41.缺失的第一个正数
难度：Hard
标签：数组、哈希表
简介：给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

题解 1 - typescript

• 编辑时间：2020-06-27
• 执行用时：72ms
• 内存消耗：33.1MB
• 编程语言：typescript
• 解法介绍：直接排序后依次判断。

function firstMissingPositive(nums: number[]): number {
  nums.sort((a, b) => a - b);
  let minNum = 1;
  for (const num of nums) {
    if (num > minNum) break;
    else if (num === minNum) minNum++;
  }
  return minNum;
}

题解 2 - typescript

• 编辑时间：2020-06-27
• 执行用时：96ms
• 内存消耗：39MB
• 编程语言：typescript
• 解法介绍：对数组进行赋值，负数赋值为 len+1,整数则在对应位置上取负。

function firstMissingPositive(nums: number[]): number {
  const len = nums.length;
  for (let i = 0; i < len; i++) if (nums[i] <= 0) nums[i] = len + 1;
  console.log(nums);
  for (let i = 0; i < len; i++) {
    const num = Math.abs(nums[i]);
    if (num <= len) nums[num - 1] = -Math.abs(nums[num - 1]);
  }
  for (let i = 0; i < len; i++) if (nums[i] > 0) return i + 1;
  return len + 1;
}

题解 3 - typescript

• 编辑时间：2021-08-15
• 执行用时：92ms
• 内存消耗：57.3MB
• 编程语言：typescript
• 解法介绍：把每个正整数放置正确的位置最后做判断。

function firstMissingPositive(nums: number[]): number {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] > n || nums[i] <= 0 || nums[nums[i] - 1] === nums[i]) break;
      [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
    }
  }
  let i = 0;
  while (i < n && nums[i] === i + 1) i++;
  return i + 1;
}

题解 4 - typescript

• 编辑时间：2021-08-15
• 执行用时：92ms
• 内存消耗：57.3MB
• 编程语言：typescript
• 解法介绍：把每个正整数放置正确的位置最后做判断。

function firstMissingPositive(nums: number[]): number {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] > n || nums[i] <= 0 || nums[nums[i] - 1] === nums[i]) break;
      [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
    }
  }
  let i = 0;
  while (i < n && nums[i] === i + 1) i++;
  return i + 1;
}