假设我们必须设计一个具有固定加热半径的标准加热器来加热所有房屋。现在,我们在水平线上给出了房屋和加热器的位置,我们必须找到加热器的最小半径,以便所有房屋都可以被这些加热器覆盖。因此,我们将分别提供房屋和加热器,我们的预期输出将是加热器的最小半径标准。
因此,如果输入类似于[1,2,3,4],[1,4],则输出将为1,因为两个加热器分别位于位置1和4。我们必须使用半径1,然后全部房屋可以加热。
为了解决这个问题,我们将遵循以下步骤-
对列表房子进行排序
对加热器列表进行排序
res:=一个与houses数组大小相同的数组,并使用inf填充
对于我在房屋大小的0范围内,
res [i]:= res [i]的最小值,| h-加热器[ind] | ,| h-加热器[ind-1] |
res [i]:= res [i]的最小值,| h-加热器[0] |
res [i]:= res [i]的最小值,| h-加热器[-1] |
h:=房屋[i]
ind:=最左边的索引将h插入加热器,以便列表保持排序
如果ind与加热器的大小相同,则
否则,如果ind与0相同,则
除此以外,
返回最大res
让我们看下面的实现以更好地理解-
from bisect import bisect_left class Solution: def findRadius(self, houses, heaters): houses.sort() heaters.sort() res = [float('inf')]*len(houses) for i in range(len(houses)): h = houses[i] ind = bisect_left(heaters, h) if ind==len(heaters): res[i] = min(res[i], abs(h - heaters[-1])) elif ind == 0: res[i] = min(res[i], abs(h - heaters[0])) else: res[i] = min(res[i], abs(h - heaters[ind]), abs(h - heaters[ind-1])) return max(res) ob = Solution()print(ob.findRadius([1,2,3,4],[1,4]))
[1,2,3,4],[1,4]
输出结果
1