題目
難度：★★☆☆☆
類型：數(shù)組
冬季已經(jīng)來臨。 你的任務(wù)是設(shè)計一個有固定加熱半徑的供暖器向所有房屋供暖。
現(xiàn)在，給出位于一條水平線上的房屋和供暖器的位置，找到可以覆蓋所有房屋的最小加熱半徑。
所以，你的輸入將會是房屋和供暖器的位置。你將輸出供暖器的最小加熱半徑。
說明:
給出的房屋和供暖器的數(shù)目是非負數(shù)且不會超過 25000。
給出的房屋和供暖器的位置均是非負數(shù)且不會超過10^9。
只要房屋位于供暖器的半徑內(nèi)(包括在邊緣上)，它就可以得到供暖。
所有供暖器都遵循你的半徑標準，加熱的半徑也一樣。
示例
示例 1:
輸入: [1,2,3],[2]
輸出: 1
解釋: 僅在位置2上有一個供暖器。如果我們將加熱半徑設(shè)為1，那么所有房屋就都能得到供暖。
示例 2:
輸入: [1,2,3,4],[1,4]
輸出: 1
解釋: 在位置1, 4上有兩個供暖器。我們需要將加熱半徑設(shè)為1，這樣所有房屋就都能得到供暖。
解答
為了找到保證所有房屋都得到供暖的暖器輻射范圍，我們需要考慮房屋與暖器的最遠距離即可。
對于每一個房屋，我們找到距離這個房屋最近的暖器，并算出距離dist；
對于所有房屋計算出的dist，取其中的最大值，即為暖器至少需要的輻射范圍。
這里，我們使用二分搜索來確定一個數(shù)字在排序列表中的位置，調(diào)用Python中的bisect模塊實現(xiàn)。例如，找到3.2在數(shù)組[1,2,3,4,5]中的位置，只需要bisect.bisect_left([1,2,3,4,5], 3.2)即可，函數(shù)返回3。
import bisect
class Solution:
def findRadius(self, houses, heaters):
res = 0
heaters.sort()
for house in sorted(houses):
idx = bisect.bisect_left(heaters, house)
if idx == 0: # 房屋house在所有暖器的左邊
dist = heaters[0] - house # 離該房屋最近的暖器就是最左邊的暖器
elif idx == len(heaters): # 房屋house在所有暖器的右邊
dist = house - heaters[-1] # 離該房屋最近的暖器就是最右邊的暖器
else: # 房屋house在暖器中間
dist = min(house-heaters[idx-1], heaters[idx]-house) # 房屋house左右最近暖器距離最小值
res = max(res, dist) # res用來統(tǒng)計最近距離的最大值
return res
如有疑問或建議，歡迎評論區(qū)留言~
