題目來源
有n個房子诵原，n個加熱器凡泣，問加熱器加熱范圍半徑得多大才可以覆蓋所有房子。
我一開始用暴力做法皮假，找出每個房子離哪個加熱器最近鞋拟，然后記錄下來，最后求一下哪個房子離所有的加熱器最遠惹资，就是我們想要的結(jié)果贺纲。
代碼如下：
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了猴誊，注意這倆數(shù)組不是有序的…我以為是有序的，搞了半天…
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;
}
};
