LC475. Heaters
Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters. So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
这题读懂了就不难啦，哦本来就是easy题(笑)。找到每个house最近的heater，结果就是最远的最近的距离。二分搜索即可。
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
// for each house, binary search the closest heaters
// result is max in distance of house to heater
Arrays.sort(heaters);
int res = 0;
for(int house: houses){
if(house < heaters[0]) res = Math.max(heaters[0] - house, res);
else if(house > heaters[heaters.length - 1]) res = Math.max(house - heaters[heaters.length-1], res);
else res = Math.max(res, nearest(heaters, house));
} // for house
return res;
}
private int nearest(int[] heaters, int house){
int low = 0, high = heaters.length - 1;
while(low <= high){
int mid = low + (high - low)/2;
if(heaters[mid] == house) return 0;
else if(heaters[mid] > house) high = mid - 1;
else low = mid + 1;
}
if(heaters[low] > house && low > 0) return Math.min(heaters[low] - house, house - heaters[low - 1]);
else if(heaters[low] < house && low < heaters.length - 1) return Math.min(house - heaters[low], heaters[low+1] - house);
return Math.abs(heaters[low] - house);
}
}
O(nlgn)