LeetCode刷题【475】供暖器

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

输入：houses = [1,5], heaters = [2]
输出：3

简单粗暴点的二分

代码

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int house : houses) {
            int l = 0;
            int r = heaters.length-1;
            int tmp = (int) 1e9+1;
            while (l<=r){
                int mid = (l + r)/2;
                //怕遗漏边缘情况不好处理就每次二分的结果都比较下
                tmp = Math.min(tmp, Math.abs(heaters[mid] - house));
                if (heaters[mid] > house){
                    r = mid-1;
                }else if (heaters[mid] < house){
                    l = mid+1;
                }else {
                    break;
                }
            }
            ans = Math.max(ans,tmp);
        }
        return ans;
    }
}