LeetCode41. 缺失的第一个正数（排序）JS

/**
 * 41. 缺失的第一个正数
 * @description 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(arr) {
  // 过滤出所有的负数和0，保留所有的正整数
  arr = arr.filter( item => item>0)
  let len = arr.length
  // 为空则表示没有正整数
  if(len === 0) return 1
  arr.sort((a,b) => a-b)
  if(arr[0] === 1){
    for(let i=0; i<len-1; i++){
      // 如果前后俩值的差值不是1，就说明不是连续的，这时候返回就行
      if(arr[i+1]-arr[i] >1){
        return arr[i]+1
      }
    }
    return arr.pop() + 1
  }else{
    return 1
  }
};

// 改进方式
var firstMissingPositive = function(arr) {
  arr = arr.filter(item => item>0)
  if(arr.length<=0) return 1
  // 选择排序，从左边找最小值
  // 冒泡排序，从右边找最大值
  // 这里用选择排序，先拿到最小值，如果是1，相邻元素差值，如果不是1，返回1
  for(let i=0, len=arr.length, min; i<arr.length; i++){
    min = arr[i];
    for(let j=i+1; j<len; j++){
      if(arr[j] < min){
        let c = min
        min = arr[j]
        arr[j] = c
      }
    }
    arr[i] = min
    if(i>0){
      if(arr[i] -arr[i-1] >1 ){
        return arr[i]-1+1
      }
    }else{
      if(min !== 1){
        return 1
      }
    }
  }
  return arr.length ? arr.pop()+1 : 1
}