475.供暖器

链接：475.供暖器
难度：Medium
标签：数组、双指针、二分查找、排序
简介：现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

题解 1 - typescript

• 编辑时间：2021-12-20
• 执行用时：108ms
• 内存消耗：42.6MB
• 编程语言：typescript
• 解法介绍：二分答案。

function bs(houses: number[], n: number, heaters: number[], m: number, rad: number): boolean {
  let idx = 0;
  for (let i = 0; i < m && idx < n; i++) {
    const heater = heaters[i];
    while (idx < n && Math.abs(heater - houses[idx]) <= rad) idx++;
  }
  return idx === n;
}
function findRadius(houses: number[], heaters: number[]): number {
  houses.sort((a, b) => a - b);
  heaters.sort((a, b) => a - b);
  const houseLen = houses.length;
  const heaterLen = heaters.length;
  let l = 0;
  let r = 1e9;
  while (l < r) {
    const m = (l + r) >> 1;
    if (bs(houses, houseLen, heaters, heaterLen, m)) r = m;
    else l = m + 1;
  }
  return l;
}

题解 2 - typescript

• 编辑时间：2021-07-23
• 执行用时：100ms
• 内存消耗：42.4MB
• 编程语言：typescript
• 解法介绍：遍历房子取最近供暖器。

function findRadius(houses: number[], heaters: number[]): number {
  heaters.sort((a, b) => a - b);
  let ans = -Infinity;
  for (const house of houses) {
    const i = bs(house);
    ans = Math.max(
      ans,
      i === 0
        ? Math.abs(heaters[i] - house)
        : i === heaters.length
        ? Math.abs(heaters[heaters.length - 1] - house)
        : Math.min(heaters[i] - house, house - heaters[i - 1])
    );
  }
  return ans;
  function bs(target: number): number {
    let l = 0;
    let r = heaters.length - 1;
    while (r - l > 3) {
      const mid = (r + l) >> 1;
      if (heaters[mid] >= target) r = mid;
      else l = mid + 1;
    }
    for (let i = l; i <= r; i++) if (heaters[i] >= target) return i;
    return heaters.length;
  }
}