题目来源
有n个房子，n个加热器，问加热器加热范围半径得多大才可以覆盖所有房子。
我一开始用暴力做法，找出每个房子离哪个加热器最近，然后记录下来，最后求一下哪个房子离所有的加热器最远，就是我们想要的结果。
代码如下：
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int n1 = houses.size(), n2 = heaters.size(), res = 0;
for (int i=0; i<n1; i++) {
int minDis = INT_MAX;
for (int j=0; j<n2; j++) {
minDis = min(minDis, abs(heaters[j] - houses[i]));
}
res = max(minDis, res);
}
return res;
}
};
然后就超时了…看了下tags，用二分，然后就AC了，注意这俩数组不是有序的…我以为是有序的，搞了半天…
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
int n1 = houses.size(), n2 = heaters.size(), res = 0;
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
for (int i=0; i<n1; i++) {
int minDis = INT_MAX;
int l = 0, r = n2 - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (heaters[mid] == houses[i]) {
minDis = 0;
break;
}
else if (heaters[mid] < houses[i]) {
l = mid + 1;
minDis = min(minDis, houses[i] - heaters[mid]);
}
else {
r = mid - 1;
minDis = min(minDis, heaters[mid] - houses[i]);
}
}
res = max(minDis, res);
}
return res;
}
};
