Binary search easy to understand, a little long


  • 1
    Z
    public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int rad = 0;
        for(int i = 0; i < houses.length; i++){
            int pre = Integer.MAX_VALUE;
            int after = Integer.MAX_VALUE;
            if(houses[i] >= heaters[heaters.length - 1]){
                pre = houses[i] - heaters[heaters.length - 1];
             }
            else if(houses[i] <= heaters[0]){
                after = heaters[0] - houses[i];
            }
            else{
                int tem = index(heaters, houses[i]);
                pre = houses[i] - heaters[tem];
                after = heaters[tem + 1] - houses[i];
            }
            
            rad = Math.max(rad, Math.min(pre, after));
        }
        return rad;
    }
    public int index(int[] heaters, int target){// find the nearest left
        int left = 0;
        int right = heaters.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(heaters[mid] <= target && heaters[mid + 1] >= target){
                return mid;
            }
            else if(heaters[mid] <= target){
                left = mid + 1;
            }
            else if(heaters[mid] >= target){
                right = mid;
            }
        }
        return left;
    }
    

    }


Log in to reply
 

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