【力扣题解】475. 供暖器

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、代码详解
  • 三、本题知识

一、题目

1、题目描述

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

2、基础框架

• Java版本框架代码如下：

class Solution {    public int findRadius(int[] houses, int[] heaters) { }}

3、原题链接

475. 供暖器

二、解题报告

1、思路分析

       (1)先对houses数组和heaters排序，遍历house数组，计算出与house[i]距离最小的供暖器的距离，对每次得到的结果取最大值即可。查找最小的距离方式为二分查找。

2、代码详解

class Solution {    public int findRadius(int[] houses, int[] heaters) { Arrays.sort(houses); Arrays.sort(heaters); int len = heaters.length - 1; int res = 0; int x = 0; for(int i = 0;i < houses.length;i++) {     if(houses[i] < heaters[0]) {  x = heaters[0] - houses[i];     }else if(houses[i] > heaters[len]) {  x = houses[i] - heaters[len];     }else {  int l = 0;  int r = len;  int ans = -1;  while(l <= r) {      int mid = (l + r) >> 1;      if(heaters[mid] <= houses[i]) {   l = mid + 1;   ans = mid;      }else {   r = mid - 1;      }  }  if(ans == len) {      x = houses[i] - heaters[ans];  }else {      x = Math.min(houses[i] - heaters[ans],heaters[ans + 1] - houses[i]);  }     }   res = Math.max(res,x); } return res;    }}

三、本题知识

二分查找