排序算法衍生4

[lynhao]

题目: 给定一个未排序的正整数数组, 找出其中没有出现的最小的正整数

eg1: [1,2,0] output: 3

eg2: [3,4,-1,1] output: 2

eg3: [11,12,14,15] output: 1

[lynhao]

解题一:

function missPositiveNumber (arr) {
  // 过滤非正整数
  arr = arr.filter(list => list > 0)

  //正整数数组为空
  if (arr.length) {
    // 排序
    arr.sort((a, b) => a -b)
    // 第一个值不是1, 则最小正整数为1
    if (arr[0] !== 1) {
      return 1
    } else {
      // 如果相邻两个数差值大于1,则最小值为第一个数加1;
      for (let i = 0, len = arr.length -1; i < len; i++) {
        if (arr[i+1] - arr[i] > 1) {
          return arr[i] + 1
        }
      }
      // 如果是连续正整数
      return arr.pop() + 1
    }  
  } else {
    return 1
  }
}

[lynhao]

符合选择排序特性, 最短可以在第一次遍历排序时就确定最小正整数

解题二:

function missPositiveNumber (arr) {
  // 过滤非正整数
  arr = arr.filter(list => list > 0)

  for (let i = 0, len = arr.length, min; i < len; i++) {
    // 先保存最小值
    min = arr[i]
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < min) {
        let temp = min
        min = arr[j]
        arr[j] = temp
      }
    }
    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
}