20180904

写一个函数find_missing(A, low, high)，给定一个范围[low,high]，寻找一个数组中缺失的元素。

find_missing([10, 12, 11, 15], 10, 15) // [13,14]
// 注: low=10 high = 15
find_missing([1, 14, 11, 51, 15],50, 55) // [50, 52, 53, 54]
// 注：low = 50, hight = 55

答案
本题考查对算法复杂度的理解，简单两次循环或者filter/map等等嵌套循环，可以在O( (high -low) * A.length )复杂度完成，但是通过排序可以优化到O(nlgn)+O(high - low)。

function find_missing(A, low, high){
  const B = A.filter(x => x >= low && x < high).sort((x,y) => x - y)
  let j = 0
  return [...Array(high - low )]
    .map((_, i) => i+low)
    .filter(x => B[j] !== x ? true : !!!++j) 
}