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 heatersarray 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.

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int radius = Integer.MIN_VALUE;

        for (int house: houses) {
            int index = binarySearch(heaters, house);
            int distLeft = index >= 1 ? house - heaters[index - 1] : Integer.MAX_VALUE;
            int distRight = index < heaters.length ? heaters[index] - house: Integer.MAX_VALUE;
            radius = Math.max(Math.min(distLeft, distRight), radius);    
        }
        return radius;
    }

    private int binarySearch(int[] heaters, int house) {
        int lo = 0; 
        int hi = heaters.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (heaters[mid] == house) {
                return mid;
            } else if (heaters[mid] < house) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    }
}

Reference

https://leetcode.com/problems/heaters/discuss/95886/Short-and-Clean-Java-Binary-Search-Solution