排序算法衍生3

[lynhao]

题目: 给定一个无序数组, 找出数组在排序之后, 相邻元素之间的最大值, 如果元素个数小于2, 则返回0

eg: [3, 6, 9, 1] output: 3

[lynhao]

解题一:

function maxDifference(arr) {
  if (arr.length < 2) {
    return 0
  }
  arr.sort((a, b) => a - b)
  let max = 0
  for (let i = 0, len = arr.length - 1, temp; i < len; i++) {
    temp = arr[i+1] - arr[i]
    if (temp > max) {
      max = temp
    }
  }
  return max
}

[lynhao]

上面解法在排序之后又遍历了一次数组,性能不是最高, 我们希望在排序的时候就知道差值

解题二:

function maxDifference(arr) {
  if (arr.length < 2) {
    return 0
  }
  let diff = 0
  let max = 0
  let len = arr.length - 1
  for (let i = len, temp; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      temp = arr[j]
      if (arr[j] > arr[j+1]) {
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
    // 第二轮才有差值
    if (i < len) {
      diff = arr[i+1] - arr[i]
      if (diff > max) {
        max = diff
      }
    }
  }
  return Math.max(max, arr[1] - arr[0])
}