这是悦乐书的第239次更新，第252篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第106题（顺位题号是475）。冬天来了！您在比赛期间的第一份工作是设计一个固定温暖半径的标准加热器，以加热所有房屋。现在，您可以在水平线上获得房屋和加热器的位置，找出加热器的最小半径，以便所有房屋都能被这些加热器覆盖。因此，您的输入将分别是房屋和加热器的位置，您的预期输出将是加热器的最小半径。例如：
输入：[1,2,3]，[2]
输出：1
说明：唯一的加热器在位置2，如果我们使用半径1标准，那么所有房屋都可以加热。
输入：[1,2,3,4]，[1,4]
输出：1
说明：两个加热器在位置1和4，我们需要使用半径1标准，然后所有房屋都可以加热。
注意：
您给出的房屋和加热器的数量是非负数，不会超过25000。
您给出的房屋和加热器的位置是非负的，不会超过10 ^ 9。
只要房子在加热器的温暖半径范围内，就可以加热。
所有加热器都遵循半径标准，温暖半径也是如此。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
我们将房子、加热器都先排序，然后利用两层循环，外层遍历房子，内层遍历加热器，每次获取到房子，就去比较对应位置的左右加热器，拿他们的位置值与当前房子的位置值之间的绝对值做比较，如果右边的加热器的位置值绝对值小于左边的，就继续向右比较，也就是取当前房子在左右加热器之间的最小半径。然后将当前的最小半径和上一次比较获得的最小半径取最大值，因为要覆盖所有的房子。
public int findRadius(int[] houses, int[] heaters) {
if (houses == null || heaters == null) {
return 0;
}
int result = Integer.MIN_VALUE;
Arrays.sort(houses);
Arrays.sort(heaters);
int i = 0, j = 0;
while (i < houses.length) {
while (j < heaters.length-1 && Math.abs(heaters[j+1] - houses[i]) <=
Math.abs(heaters[j] - houses[i])) {
j++;
}
result = Math.max(result, Math.abs(heaters[j] - houses[i]));
i++;
}
return result;
}
03 第二种解法
我们先将加热器排序，然后遍历houses中的元素，我们使用二分法找到当前房子在加热器中的最小半径，即当前位置的房子在对应位置的加热器中，其左右加热器到房子之间的最小值，然后比较所有房子的最小半径，在其中取最大值，即最大值所代表的的半径能够覆盖所有房子。
public int findRadius2(int[] houses, int[] heaters) {
if (houses == null || heaters == null) {
return 0;
}
Arrays.sort(heaters);
int result = Integer.MIN_VALUE;
for (int i=0; i<houses.length; i++) {
int rad = findOne(houses[i], heaters);
result = Math.max(result, rad);
}
return result;
}
public int findOne(int house, int[] heaters) {
int start = 0, end = heaters.length-1;
int left = Integer.MAX_VALUE, right = Integer.MAX_VALUE;
while (start <= end) {
int mid = (start+end)/2;
int heater = heaters[mid];
if (house == heater) {
return 0;
} else if (house < heater) {
right = heater - house;
end = mid - 1;
} else {
left = house - heater;
start = mid + 1;
}
}
return Math.min(left, right);
}
04 第三种解法
此解法和第二种解法的思路是一致的，也是利用二分法，只是借助Arrays类的binarySearch方法来完成。
public int findRadius3(int[] houses, int[] heaters) {
if (houses == null || heaters == null) {
return 0;
}
Arrays.sort(heaters);
int result = Integer.MIN_VALUE;
for (int house : houses) {
int index = Arrays.binarySearch(heaters, house);
if (index < 0) {
index = -(index + 1);
}
int dis = index-1 >= 0 ? house - heaters[index-1] : Integer.MAX_VALUE;
int dis2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
result = Math.max(result, Math.min(dis, dis2));
}
return result;
}
05 小结
算法专题目前已日更超过三个月，算法题文章106+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！