冬季已經來臨。 你的任務是設計一個有固定加熱半徑的供暖器向所有房屋供暖。

現在，給出位于一條水平線上的房屋和供暖器的位置，找到可以覆蓋所有房屋的最小加熱半徑。

所以，你的輸入將會是房屋和供暖器的位置。你將輸出供暖器的最小加熱半徑。

說明:

給出的房屋和供暖器的數目是非負數且不會超過 25000。
給出的房屋和供暖器的位置均是非負數且不會超過10^9。
只要房屋位于供暖器的半徑內(包括在邊緣上)，它就可以得到供暖。
所有供暖器都遵循你的半徑標準，加熱的半徑也一樣。
示例 1:

輸入: [1,2,3],[2]
輸出: 1
解釋: 僅在位置2上有一個供暖器。如果我們將加熱半徑設為1，那么所有房屋就都能得到供暖。

代碼

class Solution {public int findRadius(int[] houses, int[] heaters) {Arrays.sort(houses);Arrays.sort(heaters);int max=0;for(int house:houses)max= Math.max(max,find(house,heaters));return max;}public int find(int loc, int[] heaters) {//二分查找int l=0,n=heaters.length,r=n-1;while (l<=r){int mid=(r-l)/2+l;if(heaters[mid]==loc)return 0;else if(heaters[mid]>loc)r=mid-1;else l=mid+1;}if(l==n) return loc-heaters[n-1];//房子應該放在供暖右邊else if(r<0) return heaters[0]-loc;//房子應該放在供暖左邊else return Math.min(heaters[l]-loc,loc-heaters[r]);//比較更近的供暖} }

總結

以上是生活随笔為你收集整理的leetcode475. 供暖器（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。