题目

题目来源：力扣（LeetCode）

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

思路分析

原地置换

  1. 我们可以采取这样的思路：把元素 1 存到下标 0 的位置，把元素 2 存在下标 1 的位置，就是把元素 x 存到下标 x-1 位置，也就是让当前的元素放到正确的位置（所谓正确的位置就是数组[1, 2, 3, 4, 5, …. n]），可以看出： 位置 = 元素 - 1。

  2. 然后扫描这个数组，看看元素 1 是不是在下标为 0 的位置，元素 2 是不是在下标为 1 的位置，找到第一个 违反规则的位置，即找到第一个没有存放正确数字的位置， 那么该位置上的数字就是缺失的第一个正数

  3. 这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。

在扫描数组的过程中：

  1. 如果当前元素已经在正确的位置，就continue剪枝。

  2. 如果当前元素不在正确的位置，那就把当前的元素放到它该放的位置trueIndex，前提是这个元素要放置的位置在数组允许的索引范围内，再满足这个前提下，有两种可能：

    • 发现这个该放的位置trueIndex上的元素放置了一个正确的元素，那就不要再放了。
    • 如果trueIndex上不是正确的元素，就把这个元素与当前访问位置上的元素做交换，交换完只保证了trueIndex是正确元素，当前访问的位置上不一定是正确元素，于是需要循环执行第2步。

  3. 最后数组的样子就是 元素大小 在 数组索引范围+1 内的元素都被放到了正确的位置上。

  4. 此时从头遍历这个数组，找出缺失的第一个正数，两种情况：
    • 第一个 元素大小 不等于 索引+1 的元素。
    • 元素都在各自的正确位置上，那就返回数组长度+1
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var firstMissingPositive = function (nums) {
  6.   const len = nums.length;
  7.   for (let i = 0; i < len; ++i) {
  8.     // 如果当前元素已经在正确的位置，就continue剪枝。
  9.     if (nums[i] == i + 1) continue;
  10.     //这里用while是因为交换回来的值不一定是"值配其位"的，那么就可能还需要进行交换
  11.     //比如[4,1,2,3]
  12.     // 1.第一次将4与3交换，形成[3,1,2,4]，明显3是"值不配位"的，也满足条件，进入新的交换
  13.     // 2.第二次将3与2交换，形成[2,1,3,4]，明显2也是"值不配位"的，且满足条件，进入新的交换
  14.     // 3.第三次将2与1交换，形成[1,2,3,4]，值全都配位了，后面的while也就都不会进了
  15.     // (此处也说明while循环不会每一次都把数组里面的所有元素都看一遍。如果有一些元素在这一次的循环中
  16.     // 被交换到了它们应该在的位置，那么在后续的遍历中，由于它们已经在正确的位置上了，代码再执行到它们
  17.     // 的时候，就会被跳过。----引用自@liweiwei1419的题解)
  18.     //**所以此处不能用if**
  19.     while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
  20.       //将出现的值都交换到相应的位置上，组成一个近似排序的数组
  21.       //其中的负数和大于数组长度的值都可以不用管，因为它是作为一个出口存在的
  22.       //这里值1放在索引0上，即值(i)需要放在索引(i-1)上
  23.       // const temp = nums[nums[i] - 1];
  24.       // nums[nums[i] - 1] = nums[i];
  25.       // nums[i] = temp;
  26.       let ind = nums[i] - 1;
  27.       [nums[i], nums[ind]] = [nums[ind], nums[i]];
  28.     }
  29.   }
  30.   for (let i = 0; i < len; ++i) {
  31.     //第一个不满足 值(nums[i])=索引(i+1) 的值所在索引(i)+1即最小未出现的正整数
  32.     //注意：以下的例子都是经过换位之后
  33.     //例1：[1,2,3,4] 这个例子是完全排序的数组，且每个位置都正确，那么就应该返回数组长度+1，而不是3+1
  34.     //例2：[1,-1,3,4] 其中-1是第一个也是唯一一个"值不配位"的值，那么它所占的位置就是未出现的最小正整数
  35.     //例3：[5,11,7,9] 这个例子是完全没有进入while排序的，因为他们所有的值都"值不配位"，那么同上面的例2，
  36.     // 第一个"值不配位"的值所占的位置就是未出现的最小正整数
  37.     if (nums[i] != i + 1) {
  38.       return i + 1;
  39.     }
  40.   }
  41.   // 都正确则返回数组长度 + 1
  42.   return len + 1;
  43. }