Heaters
Binary Search
Solution & Analysis
Via @yhteng
这题主要有两个点:
第一个是如何确定离某一个house最近的heater并记录它们之间的距离,这些距离所构成的集合中的最大值就是答案。从算法上来看,比较合理的做法是遍历houses集合,并找到每一个house对应最近的heater以及它们之间的距离,所以本质上是针对每个house,找到其在heaters数组中的插入位置,变成了insert into an sorted array的问题。
第二个是插入排序数组的问题,如果逐个遍历heaters中的每个元素(包括双指针),那么复杂度是o(n),这里可以采用二分法来查找,进而得到o(logn)的复杂度。
给定每个house 位置找到离他最近的heater,然后求出该radius。将所有的radius求个最大值即为结果。
在对每个house找closest heater时,利用二分法。先sort heater,然后在该heater中找到和house pos 最接近的值即为最小radius。
Via @shawngao
The idea is to leverage decentArrays.binarySearch()
function provided by Java.
1. For each house
, find its position between those heaters
(thus we need the heaters
array to be sorted).
2. 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.
3. 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.
Binary Search + Loop
这里的Binary Search也可以使用Arrays.binarySearch(int[] a, t); 但是要处理返回的index,index可能为-1.
Reference
https://leetcode.com/problems/heaters/discuss/95886/Short-and-Clean-Java-Binary-Search-Solution
Last updated