https://leetcode.com/problems/heaters/
http://www.cnblogs.com/grandyang/p/6181626.html
X. https://leetcode.com/problems/heaters/discuss/95886/Short-and-Clean-Java-Binary-Search-Solution
X.
主要思路为对每一个房间，寻找离他最近的加热器，统计这些房间与离他最近的加热器的距离，在这些距离中取最大值即为所求。
具体实现的话，首先对加热器的位置进行排序，按照从小到大的顺序。然后对每一个房间，在加热器数组中用二分查找算法找到离他最近的加热器的位置，计算距离并更新目标半径。
另外，我用的二分查找为”在数组中找到最后一个小于等于目标值的下标，若不存在则返回-1“，因此除了二分查找得到的下标 index 对应的加热器与该房间距离，还要比较下标为 index + 1 的加热器与房间的距离，取两者之间较小值。
https://discuss.leetcode.com/topic/71460/short-and-clean-java-binary-search-solution
X. Two Pointers
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
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.
Note:
- Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
- Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
- As long as a house is in the heaters' warm radius range, it can be warmed.
- All the heaters follow your radius standard and the warm radius will the same.
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.
Example 2:
Input: [1,2,3,4],[1,4] Output: 1 Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.https://blog.csdn.net/elliott_yoho/article/details/78578277
题意大致为，在一条水平线上有若干房间和加热器，给定房间和加热器的坐标，求加热器所需的最小供暖范围，使得所有房间有加热器为其供暖。
http://www.cnblogs.com/grandyang/p/6181626.html
这道题是一道蛮有意思的题目，首先我们看题目中的例子，不管是houses还是heaters数组都是有序的，所以我们也需要给输入的这两个数组先排序，以免其为乱序。我们就拿第二个例子来分析，我们的目标是houses中的每一个数字都要被cover到，那么我们就遍历houses数组，对每一个数组的数字，我们在heaters中找能包含这个数字的左右范围，然后看离左右两边谁近取谁的值，如果某个house位置比heaters中最小的数字还小，那么肯定要用最小的heater去cover，反之如果比最大的数字还大，就用最大的数字去cover。对于每个数字算出的半径，我们要取其中最大的值。通过上面的分析，我们就不难写出代码了，我们在heater中两个数一组进行检查，如果后面一个数和当前house位置差的绝对值小于等于前面一个数和当前house位置差的绝对值，那么我们继续遍历下一个位置的数。跳出循环的条件是遍历到heater中最后一个数，或者上面的小于等于不成立，此时heater中的值和当前house位置的差的绝对值就是能cover当前house的最小半径，我们更新结果res即可
X. https://leetcode.com/problems/heaters/discuss/95886/Short-and-Clean-Java-Binary-Search-Solution
The idea is to leverage decent
Arrays.binarySearch() function provided by Java.- For each
house, find its position between thoseheaters(thus we need theheatersarray to be sorted). - Calculate the distances between this
houseand leftheaterand rightheater, get aMINvalue of those two values. Corner cases are there is no left or right heater. - Get
MAXvalue among distances in step 2. It's the answer.
Time complexity: max(O(nlogn), O(mlogn)) - m is the length of houses, n is the length of heaters.
I am sharing my solution. The idea is to find the closest heater to each house and take maximum of the closest distances. Thus initially it is necessary to sort both houses and heaters by their coordinates. Then assign two pointers, one for houses and another for heaters. Then start traversing the houses. If the ith house is located between j-1th heater and jth heater, then take distance to the closest one and check whether it is the maximum radius found so far. The corner cases are when a house is located before the 1st heater, and when a house is located after the last heater. At the corner case position, there are only distance to consider. That's it. I think code will clarify the idea more. public int findRadius(int[] houses, int[] heaters) {
if(houses == null || houses.length == 0) return 0;
Arrays.sort(houses);
Arrays.sort(heaters);
int ans = 0;
int i = 0;
int j = 0;
while(i<houses.length){
if(houses[i] <= heaters[j]){ //if house is located before heater j.
if(j == 0){ // corner case when the heater is the first one
ans = Math.max(ans, heaters[j]-houses[i]);
i++;
continue;
}
} else { // if house is located after some heater,
while(j!=heaters.length-1 && heaters[j]<houses[i]){ // then find a heater that stands after the house
j++;
}
if(j == 0 || heaters[j] < houses[i]){ // corner cases if j is 0 or there is no more heaters
ans = Math.max(ans, houses[i]-heaters[j]);
i++;
continue;
}
}
int dist = Math.min(houses[i]-heaters[j-1], heaters[j]-houses[i]); // if house is located between jth and j-1th heaters
ans = Math.max(ans, dist);
i++;
}
return ans;
}X.
主要思路为对每一个房间，寻找离他最近的加热器，统计这些房间与离他最近的加热器的距离，在这些距离中取最大值即为所求。
具体实现的话，首先对加热器的位置进行排序，按照从小到大的顺序。然后对每一个房间，在加热器数组中用二分查找算法找到离他最近的加热器的位置，计算距离并更新目标半径。
另外，我用的二分查找为”在数组中找到最后一个小于等于目标值的下标，若不存在则返回-1“，因此除了二分查找得到的下标 index 对应的加热器与该房间距离，还要比较下标为 index + 1 的加热器与房间的距离，取两者之间较小值。
https://discuss.leetcode.com/topic/71460/short-and-clean-java-binary-search-solution
The idea is to leverage decent Arrays.binarySearch() function provided by Java.
- For each house, find its position between those heaters (thus we need the heaters array to be sorted).
- Calculate the distances between this house and left heater and right heater, get a MIN value of those two values. Corner cases are there is no left or right heater.
- Get MAX value among distances in step 2. It's the answer.
Time complexity: max(O(nlogn), O(mlogn)) - m is the length of houses, n is the length of heaters.
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int result = Integer.MIN_VALUE;
for (int house : houses) {
int index = Arrays.binarySearch(heaters, house);
if (index < 0) {
index = -(index + 1);
}
int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
result = Math.max(result, Math.min(dist1, dist2));
}
return result;
}
Just a small variation (we can ignore houses on heaters, and I like
~):public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int result = 0;
for (int house : houses) {
int index = Arrays.binarySearch(heaters, house);
if (index < 0) {
index = ~index;
int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
result = Math.max(result, Math.min(dist1, dist2));
}
}
return result;
}
X. TreeSet
Initially I was trying TreeSet as it provides easier way to find the lowerBound and upperBound. While I mistakenly reversed the min and max relationship when updating the global min radius result. Thanks to @ckcz123 's solution and I realized my error and made it right.
The idea using TreeSet is first put heaters' location into the tree, then iterate the houses' location finding the smallest radius with which one of the closest heaters may cover. Say heaters[1, 4] , houses[1,2,3,4]. When we scan the house = 1, found closest heater is at 1, so the global max till house at 1 is 0; then when house = 2, found the closest heater is min(house at 2 - heater at 1, heater at 4 - house at 2) = 1, which means the heater at 1 can cover the house at 2 and we do not need to use heater at 4. In the end, we may found the global res (min radius required) and remember that some of the heaters may not be effectively used as long as all the houses are already covered. O(logn) for TreeSet operations in this solution, but need O(heater) space which is not as good as binary search solution.
The idea using TreeSet is first put heaters' location into the tree, then iterate the houses' location finding the smallest radius with which one of the closest heaters may cover. Say heaters[1, 4] , houses[1,2,3,4]. When we scan the house = 1, found closest heater is at 1, so the global max till house at 1 is 0; then when house = 2, found the closest heater is min(house at 2 - heater at 1, heater at 4 - house at 2) = 1, which means the heater at 1 can cover the house at 2 and we do not need to use heater at 4. In the end, we may found the global res (min radius required) and remember that some of the heaters may not be effectively used as long as all the houses are already covered. O(logn) for TreeSet operations in this solution, but need O(heater) space which is not as good as binary search solution.
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
TreeSet<Integer> treeset = new TreeSet<>();
for (int heater : heaters) treeset.add(heater);
int res = 0;
for (int house : houses) {
Integer upper = treeset.ceiling(house);
Integer lower = treeset.floor(house);
res = Math.max(res, Math.min(upper == null ? Integer.MAX_VALUE : upper - house, lower == null ? Integer.MAX_VALUE : house - lower));
}
return res;
}
}
Based on 2 pointers, the idea is to find the nearest heater for each house, by comparing the next heater with the current heater.
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int i = 0, j = 0, res = 0;
while (i < houses.length) {
while (j < heaters.length - 1
&& Math.abs(heaters[j + 1] - houses[i]) <= Math.abs(heaters[j] - houses[i])) {
j++;
}
res = Math.max(res, Math.abs(heaters[j] - houses[i]));
i++;
}
return res;
}
Updated solution inspired by @StefanPochmann
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int i = 0, res = 0;
for (int house : houses) {
while (i < heaters.length - 1 && heaters[i] + heaters[i + 1] <= house * 2) {
i++;
}
res = Math.max(res, Math.abs(heaters[i] - house));
}
return res;
}Example: h = house, * = heater M = INT_MAX
h h h h h h h h h houses
1 2 3 4 5 6 7 8 9 index
* * * heaters
0 2 1 0 1 0 - - - (distance to nearest RHS heater)
0 1 2 0 1 0 1 2 3 (distance to nearest LHS heater)
0 1 1 0 1 0 1 2 3 (res = minimum of above two)
Result is maximum value in res, which is 3.
*/
int findRadius(vector<int>& A, vector<int>& H) {
sort(A.begin(), A.end());
sort(H.begin(), H.end());
vector<int> res(A.size(), INT_MAX);
// For each house, calculate distance to nearest RHS heater
for (int i = 0, h = 0; i < A.size() && h < H.size(); ) {
if (A[i] <= H[h]) { res[i] = H[h] - A[i]; i++; }
else { h++; }
}
// For each house, calculate distance to nearest LHS heater
for (int i = A.size()-1, h = H.size()-1; i >= 0 && h >= 0; ) {
if (A[i] >= H[h]) { res[i] = min(res[i], A[i] - H[h]); i--; }
else { h--; }
}
return *max_element(res.begin(), res.end());
}
}