LeetCode 041. 缺失的第一个正数

题目描述:

难度：Hard

相关话题：数组

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

示例1:

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

示例2:

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

示例3:

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

说明:

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

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区

---

思路：

将每一个数字放到它应该存在的位置，如果nums[i]<=0或者nums[i]>n(n为当前数组的长度)，不处理，因此如果存在以上的数字，那么最最终结果一定在[1,n]之间。

因此，只需要对[1,n]内部的数字放到对应的num-1索引上，例如1就应该放到索引0上。

通过交换将数字都放好后，对数字遍历查询，如果找到中间某个数字不连续A[i]!==i+1，那么就是结果，如果不能存在不连续的数字，返回n。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(A) {
  let n=A.length
  for(let i=0;i<n;i++){
    while(A[i]>0 && A[i]<=n && A[A[i] - 1]!==A[i]){
      swap(i, A[i]-1)
    }
  }
  for(let i=0;i<n;i++){
    if(A[i]!==i+1)return i+1
  }
  return n+1

  function swap(i,j){
    let t=A[i]
    A[i]=A[j]
    A[j]=t
  }
};