题目描述
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
现在,给出位于一条水平线上的房屋和供暖器的位置,找到可以覆盖所有房屋的最小加热半径。
所以,你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。
说明
- 给出的房屋和供暖器的数目是非负数且不会超过 25000。
- 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
- 只要房屋位于供暖器的半径内(包括在边缘上),它就可以得到供暖。
- 所有供暖器都遵循你的半径标准,加热的半径也一样。
样例1
输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。
样例2
输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1,这样所有房屋就都能得到供暖。
算法1
(排序+二分) $O((n + m)\log m)$
理解题意后我们可以发现我们需要做的是对于每个房屋,找到离它最近的供暖器,然后计算距离,最后取所有房屋距离的最大值就是最小半径。而找到每个房屋最近的供暖器可以通过找到它左右两边靠得最近的供暖器来得到,因此我们可以将 $heaters$ 先排序,然后遍历 $houses$ ,对每个 $houses[i]$ 我们找到第一个大于等于它的供暖器和最后一个小于它的供暖器,这两个距离取最小值就是这个房屋最近的供暖器。
时间复杂度
假设 $houses$ 数组长度为 $n$ ,$heaters$ 数组长度为$m$,排序需要$O(m\log m)$的时间,而找到每个房屋最近的供暖器需要$O(n\log m)$的时间,总时间复杂度为$O((n + m)\log m)$。
C++ 代码
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int res = 0;
sort(heaters.begin(), heaters.end());
sort(houses.begin(), houses.end());
for (int i = 0; i < houses.size(); i ++ ) {
auto right = lower_bound(heaters.begin(), heaters.end(), houses[i]);
auto left = right;
int r = right == heaters.end() ? INT_MAX : *right - houses[i];
int l = left == heaters.begin() ? INT_MAX : houses[i] - *(left - 1);
res = max(res, min(l, r));
}
return res;
}
};
算法2
(排序+双指针) $O(n\log n + m\log m)$
可以观察到该题具有单调性,我们分别将 $houses$ 和 $heaters$ 排序后,那么对于每个 $houses[i]$,$heaters$数组中每个数与它的距离一定是先单调递减再单调递增的,所以肯定存在一个最优的 $heaters[j]$ ,使得 $heaters[j]$ 与 $houses[i]$ 距离最近。我们可以通过比较 $heaters[j]$ 和 $heaters[j + 1]$ 与 $houses[i]$ 的距离大小关系来找到这个极小值点。
而当 $i$ 往后移动时,对于 $houses[i + 1]$ 而言,最优的 $j’$ 一定大于等于 $j$。证明如下:
- 如果 $heaters[j] \le houses[i]$,那么由于 $houses[i + 1] \ge houses[i]$,如果 $heaters[j’] <= heaters[j]$,$houses[i + 1] - heaters[j’] >= houses[i + 1] - heaters[j]$,与 $j’$最优矛盾。
- 如果 $heaters[j] \gt houses[i]$,那么若 $houses[i + 1] \le heaters[j]$,则 $j’ = j$。若 $houses[i + 1] \gt heaters[j]$,则 $j’ >= j$。
时间复杂度
对两个数组排序需要 $O(n\log n + m\log m)$ 的复杂度,双指针扫描需要 $O(m + n)$ 的复杂度。总时间复杂度为 $O(n\log n + m\log m)$ 。
C++ 代码
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int n = heaters.size();
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int res = 0;
for (int i = 0, j = 0; i < houses.size(); i ++ ) {
while (j < n - 1 &&
(abs(houses[i] - heaters[j]) >= abs(houses[i] - heaters[j + 1])))
j ++ ;
res = max(res, abs(houses[i] - heaters[j]));
}
return res;
}
};