475. Heaters

AC code

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
  const sortedHeaters = heaters.sort((a, b) => a - b);
  return houses.reduce((p, e) => {
    let left = Infinity,
      right = Infinity;
    for (let i = 0; i < sortedHeaters.length; i++) {
      if (sortedHeaters[i] <= e) {
        left = e - sortedHeaters[i];
      }
      if (sortedHeaters[i] >= e) {
        right = sortedHeaters[i] - e;
        break;
      }
    }
    const min = Math.min(left,right)
    return Math.max(min, p);
  }, 0);
};

too slow….

O(n^2)

how can we improve ?

这个进行了两次遍历和一次快排。。。

优化 两次排序后我们不用每次都从1开始map

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
  const sortedHouses = houses.sort((a, b) => a - b);
  const sortedHeaters = heaters.sort((a, b) => a - b);

  let j = 0,
    ans = 0,
    a = sortedHouses.length,
    b = sortedHeaters.length;

  for (let i = 0; i < a; i++) {
    let pos = sortedHouses[i],
      minDis = Infinity;
    while (sortedHeaters[j] < pos && j < b - 1) j++;

    j > 0 && (minDis = Math.min(minDis, Math.abs(pos - heaters[j - 1])));
    minDis = Math.min(minDis, Math.abs(pos - heaters[j]));

    ans = Math.max(ans, minDis);

    j > 0 && j--;
  }

  return ans;
};