一【题目类别】

双指针

二【题目难度】

中等

三【题目编号】

475.供暖器

四【题目描述】

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

五【题目示例】

示例 1:
- 输入: houses = [1,2,3], heaters = [2]
- 输出: 1
- 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
- 输入: houses = [1,2,3,4], heaters = [1,4]
- 输出: 1
- 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
示例 3：
- 输入：houses = [1,5], heaters = [2]
- 输出：3

六【解题思路】

本题思路不太好想，但是把逻辑理顺之后，代码并不难写
首先我们应该对两个数组进行排序，排序的目的是减少不必要的比较以及避免比较时出错，因为如果不排序可能会导致最短距离找不到，这个可以在纸上用笔简单画一画就明白了
排序之后遍历房屋数组和供暖器数组，但是两个数组遍历的方式不太一样：
- 房屋数组：从0开始遍历，遍历到数组结尾，此遍历的主要目的是从头到尾求出每个房子距离供暖器的最短距离
- 供暖器数组：从0开始遍历，遍历到数组结尾的前一个，此遍历的目的是找到距离每个房子最近的供暖器
遍历数组之后，我们就可以得到距离某个房子最近的供暖器了
但是此时我们还没有结束，我们要继续将剩下的所有房屋遍历结束
将所有房屋遍历结束后，我们从所有最小的距离中选出最大的距离就是我们的答案
最后返回结果即可

七【题目提示】

1<=houses.length,heaters.length<=3∗1041 <= houses.length, heaters.length <= 3 * 10^41<=houses.length,heaters.length<=3∗104
1<=houses[i],heaters[i]<=1091 <= houses[i], heaters[i] <= 10^91<=houses[i],heaters[i]<=109

八【时间频度】

时间复杂度：O(mlogm+nlogn)O(mlogm+nlogn)O(mlogm+nlogn)，其中mmm和nnn分别为传入的两个数组的长度
空间复杂度：O(logm+logn)O(logm+logn)O(logm+logn)，其中mmm和nnn分别为传入的两个数组的长度

九【代码实现】

Java语言版

class Solution {public int findRadius(int[] houses, int[] heaters) {Arrays.sort(houses);Arrays.sort(heaters);int res = 0;for(int i = 0,j = 0;iint curDis = Math.abs(houses[i] - heaters[j]);while(j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])){j++;curDis = Math.min(curDis,Math.abs(houses[i] - heaters[j]));}res = Math.max(curDis,res);}return res;}
}

C语言版

int compare(const void *a,const void *b)
{int *pa = (int*)a;int *pb = (int*)b;return *pa - *pb;
}int findRadius(int* houses, int housesSize, int* heaters, int heatersSize)
{qsort(houses,housesSize,sizeof(int),compare);qsort(heaters,heatersSize,sizeof(int),compare);int res = 0;for(int i = 0,j=0;iint curDis = fabs(houses[i] - heaters[j]);while(j < heatersSize - 1 && fabs(houses[i] - heaters[j]) >= fabs(houses[i] - heaters[j + 1])){j++;curDis = fabs(houses[i] - heaters[j]);}res = fmax(res,curDis);}return res;
}

Python语言版

class Solution:def findRadius(self, houses: List[int], heaters: List[int]) -> int:houses.sort()heaters.sort()lenHouses = len(houses)lenHeaters = len(heaters)res = 0j = 0for i in range(0,lenHouses):curDis = abs(houses[i] - heaters[j])while j < lenHeaters - 1 and abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1]):j+=1curDis = abs(houses[i] - heaters[j])res = max(res,curDis)return res

C++语言版

class Solution {
public:int findRadius(vector& houses, vector& heaters) {sort(houses.begin(),houses.end());sort(heaters.begin(),heaters.end());int res = 0;for(int i = 0,j=0;iint curDis = abs(houses[i] - heaters[j]);while(j < heaters.size() - 1 && abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1])){j++;curDis = abs(houses[i] - heaters[j]);}res = max(res,curDis);}return res;}
};