Heaters [source code]
public class Heaters {
static
/******************************************************************************/
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int maxDistance = 0;
for (int i = 0; i < houses.length; i++) {
int nearestDistance = getNearestDistance(houses[i], heaters);
if (nearestDistance > maxDistance) maxDistance = nearestDistance;
}
return maxDistance;
}
public int getNearestDistance(int pos, int[] heaters) {
int lo = 0, hi = heaters.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (heaters[mid] == pos) return 0;
else if (pos < heaters[mid]) hi = mid - 1;
else lo = mid + 1;
}
if (lo == 0) return heaters[0] - pos;
else if (lo == heaters.length) return pos - heaters[heaters.length - 1];
else return Math.min(pos - heaters[lo - 1] , heaters[lo] - pos);
}
}
/******************************************************************************/
public static void main(String[] args) {
Heaters.Solution tester = new Heaters.Solution();
int[][] inputs = {
{1,2,3}, {2}, {1},
{1,2,3,4}, {1,4}, {1},
{282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923}, {823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612}, {161834419},
};
for (int i = 0; i < inputs.length / 3; i++) {
int[] houses = inputs[3 * i];
int[] heaters = inputs[1 + 3 * i];
int expected = inputs[2 + 3 * i][0];
int output = tester.findRadius(houses, heaters);
System.out.println(Printer.seperator());
Printer.openColor("magenta");
System.out.print(Printer.array(houses) + " AND " + Printer.array(heaters));
Printer.closeColor();
System.out.print(" -> " + output);
Printer.openColor(output == expected ? "green" : "red");
System.out.println(", expected: " + expected);
Printer.closeColor();
}
}
}
这个题目没有说给的两个array是不是sorted的, 不过这个题目看起来也有点复杂, 可以先用sorting来做, 就当做是笨办法了; //好像不是sorted的, 所以自己要sort一下, 注意的是只有heaters需要sort, houses并不需要;
Binary Search的标准写法最后lo的位置返回的是如果unfound的情况下合理的insert位置, 这个好像之前总结过一次了;
这里还有一个问题以前没有总结过, 如果这个unfounded是要找的这个key比array里面所有的entry都大的情况下, lo的值其实是length, 这个自己试一下就知道了. 所以如果想要对miss的情况进行妥善的处理, 那么这个值也要考虑, 因为在这个值的时候, 严格来说lo不能说是the right position to insert.
最后的速度是28ms (53%). 因为这个算法本身只有O(NlgN), 所以刚开始submit的时候忘记把log信息删除, 直接超时了. 这个有时候也要注意一下, 看到超时不要立刻就慌, 先看看是不是log忘记删除了;
除此以外, 整个题目思路还是很简单的.
这个是discussion里面调用API做的一个:
public class Solution {
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;
}
}
原理是差不多的;
According to Java doc : https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[], int)
Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
另外这里的
index = -(index + 1);
可以改成
index = ~index;
小技巧而已, 不用纠结;
这是discussion里面另外一个线性搜索的:
public class Solution {
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[index+1] - house < house - heaters[index]) {
i++;
}
res = Math.max(res, Math.abs(heaters[i] - house));
}
return res;
}
}
注意heaters[index+1] - house < house - heaters[index]这里加绝对值也可以, 不加其实也可以;
这个的搜索是线性的, 所以这个的速度其实不好. 另外他其实也没有必要sort houses;
这个是另外一个用TreeSet来做sorting的:
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;
}
}
没有什么特别的地方, 就是TreeSet的这个API的使用熟悉一下; 另外这个算法的空间复杂度其实不如Binary Search;
Problem Description
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.
Difficulty:Easy
Total Accepted:17.1K
Total Submissions:58K
Contributor: neelamgehlot
Companies
google
Related Topics
binary search