这是悦乐书的第 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 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/50b12f8b0f64