一、题目描述
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在,给出位于一条水平线上的房屋 houses
和供暖器 heaters
的位置,请你找出并返回可以覆盖所有房屋的最小加热半径。
注意:所有供暖器 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
提示:
1 <= houses.length, heaters.length <= 3 * 10^4
1 <= houses[i], heaters[i] <= 10^9
二、解题思路
- 对供暖器的位置进行排序。
- 遍历每个房屋,找到距离该房屋最近的供暖器。这可以通过二分查找实现,因为供暖器的位置是有序的。
- 对于每个房屋,计算其与最近供暖器的距离,并更新最大距离。
- 最后,最大距离就是可以覆盖所有房屋的最小加热半径。
三、具体代码
import java.util.Arrays;
class Solution {
public int findRadius(int[] houses, int[] heaters) {
// 对供暖器位置进行排序
Arrays.sort(heaters);
int maxRadius = 0;
// 遍历每个房屋
for (int house : houses) {
// 使用二分查找找到距离当前房屋最近的供暖器
int left = 0, right = heaters.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (heaters[mid] < house) {
left = mid + 1;
} else {
right = mid;
}
}
// 计算当前房屋与最近供暖器的距离
int distance = Math.abs(heaters[left] - house);
// 如果left不是第一个供暖器,计算当前房屋与左边供暖器的距离,取较小值
if (left > 0) {
distance = Math.min(distance, house - heaters[left - 1]);
}
// 更新最大距离
maxRadius = Math.max(maxRadius, distance);
}
return maxRadius;
}
}
在这段代码中,我们首先对供暖器的位置进行排序,然后遍历每个房屋,使用二分查找找到距离该房屋最近的供暖器,并计算距离。如果当前供暖器不是第一个供暖器,我们还需要计算房屋与左边供暖器的距离,并取较小值。最后,我们将计算出的距离与当前最大距离进行比较,并更新最大距离。最终返回的最大距离就是可以覆盖所有房屋的最小加热半径。
四、时间复杂度和空间复杂度
1. 时间复杂度
-
对供暖器位置进行排序的时间复杂度为 O(m log m),其中 m 是供暖器的数量。
-
遍历每个房屋的时间复杂度为 O(n),其中 n 是房屋的数量。
-
在每次遍历房屋时,我们使用二分查找来找到距离当前房屋最近的供暖器,二分查找的时间复杂度为 O(log m)。
将上述步骤合并,总的时间复杂度为 O(m log m + n log m)。由于 m 和 n 是输入规模,因此可以简化为 O((m + n) log m)。
2. 空间复杂度
-
排序供暖器位置使用的空间复杂度为 O(1),因为排序是在原数组上进行的(假设使用的排序算法是原地排序)。
-
代码中使用了几个基本类型的变量(left, right, mid, distance, maxRadius),它们使用的空间是常数级别的,因此空间复杂度为 O(1)。
综上所述,该算法的时间复杂度为 O((m + n) log m),空间复杂度为 O(1)。其中 m 是供暖器的数量,n 是房屋的数量。
五、总结知识点
-
数组的排序:
- 使用
Arrays.sort()
方法对数组进行排序,这是一个常用的内置方法,它基于快速排序算法。
- 使用
-
二分查找算法:
- 通过二分查找找到数组中第一个大于或等于特定值的元素,这是算法中的一个高效查找方法。
-
循环和条件判断:
- 使用
for
循环遍历房屋数组。 - 使用
while
循环和条件判断来实现二分查找的逻辑。
- 使用
-
数学运算:
- 使用
Math.abs()
方法计算绝对值,即两个数之间的距离。 - 使用
Math.min()
方法取两个数中的最小值。 - 使用
Math.max()
方法更新最大值。
- 使用
-
数组索引操作:
- 通过索引访问数组元素,以及判断索引的有效性(例如,检查
left > 0
来确保不会越界)。
- 通过索引访问数组元素,以及判断索引的有效性(例如,检查
-
基本数据类型:
- 使用
int
类型的变量来存储索引、距离和最大半径。
- 使用
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
标签:heaters,供暖,--,复杂度,距离,房屋,475,LeetCode,left From: https://blog.csdn.net/weixin_62860386/article/details/144510998