Yet another Java solution using self implemented binary search


  • 0
    O
    public class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            Arrays.sort(houses);
            Arrays.sort(heaters);
            int r = 0;
            for (int pos : houses) {
                int f = bsearch(heaters, pos, true);
                int c = bsearch(heaters, pos, false);
                
                r = Math.max(r, Math.min(Math.abs(pos - heaters[f]), Math.abs(pos - heaters[c])));
            }
            return r;
        }
        
        private int bsearch(int[] nums, int target, boolean option) {
            int l = 0;
            int r = nums.length - 1;
            
            while (l <= r) {
                int m = l + (r - l) / 2;
                
                if (target == nums[m]) return m;
                else if (target > nums[m]) l = m + 1;
                else r = m - 1;
            }
            
            return option ? Math.min(l, nums.length - 1) : Math.max(r, 0);
        }
    }
    

Log in to reply
 

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