Java AC solution: using Self-implemented Binary Search


  • 0

    The main idea is similar to most binary-search-based solutions: sort the heaters, then iterate the houses, find the closest heater, then find the max distance overall.

    Instead of using the Arrays.binarySearch standard utility that automatically returns the right position to insert if not found, I implemented the binary search myself which returns the correct distance to closest heater directly.

    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);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.