leetcode375

leetcode375

public class findRadius475 {
    /**
     * 刚开始的想法是要遍历每个加热器，所以思路就是错的，我们的肯本目标是让房子有暖气，所以应该遍历房子
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int house : houses) {
            int right = binarySearch(heaters,house);
            int left = right - 1;
            int leftIndex = left <0? Integer.MAX_VALUE:house - heaters[left];
            int rightIndex = right >=heaters.length? Integer.MAX_VALUE:heaters[right] - house;
            ans = Math.max(Math.min(leftIndex,rightIndex),ans);
        }
        return ans;
    }

    /**
     * 寻找第一个大于等于target的下标
     * @param heaters
     * @param target
     * @return
     */
    public int binarySearch(int[] heaters,int target){
        int left = 0;
        int right = heaters.length -1;
        if(heaters[right] < target){
            return right + 1;
        }
        while(left < right){
            int mid = (left + right) / 2;
            if(heaters[mid] >= target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        findRadius475 x = new findRadius475();
        x.findRadius(new int[]{1,5},new int[]{2,6});
    }
}