[leetcode]41.缺失的第一个正数

[MagicalBridge]

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

示例 1:

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

示例 2:

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

示例 3:

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

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

思考:
如果这道题目没有额外的时间和空间复杂度的要求，其实比较容易实现：

• 我们可以将所有的数组放入哈希表，随后从1开始依次枚举正数，并判断是否在哈希表中；
• 我们可以从1开始依次枚举正整数，并遍历数组，判断其是否在数组中。

方法一:

• 我们只需要从最小的正整数1开始，依次判断 2、3、4直到数组的长度N是否在数组中;
• 如果当前考虑的数不再这个数组中，我们就找到了这个缺失的最小正整数；
• 由于我们需要依次判断某一个正整数是否在这个数组里面，我们可以先把这个数组中所有的元素放进哈希表，接下来再遍历的时候，可以按照�O(1)的时间复杂度判断某个正整数是否在这个数组中；
• 由于题目要求，我们只能使用常数级别的空间，而哈希表的大小与数组的长度是线性相关的，因此空间复杂度不符合题目要求。

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
  // 创建一个set 这里使用se目的和哈希表一样，优点在于并不关心数组中的重复元素
  let set = new Set();
  // 遍历数组, 将数组中的元素放入 set 中
  nums.forEach(x => set.add(x)) 
  // 初始化假设 1 就是缺失的第一个正整数
  let res = 1; 
  // 数组中第一个没有元素的位置
  let n = nums.length;
  // 这里需要注意一个细节 <= 假设 数组是[1,2,3,4] 缺失的第一个
  // 正数就是5,那么正好是n所在的位置
  while(res <= n) {
    // 如果set中存放的数组元素不包含 res 说明就是缺失的
    if (set.has(res) === false) {
      return res;
    } else {
      res++;
    }
  }
  return res;
}

复杂度分析：

• 时间复杂度：O(N)，这里 N 表示数组的长度。
• 空间复杂度：O(N)，把 N 个数存在哈希表里面，使用了 N 个空间。