供暖器(Leetcode 475)

1

题目分析

   最近忙于论文,停更了一段时间,现在继续我们的刷题之旅。我们要寻找最小的加热半径,因为每一个房屋都需要加热到,因此我们找到距离每个房屋最近的供暖器到该房屋之间的距离,并求所有距离的最大值即可。

二分查找

这个题目有一个小技巧,为了方便二分查找对于边界值的讨论,我们可以在正无穷和负无穷远处加上两个供暖器,这样就不会超出边界,也不用对特殊值进行分类讨论

算法的**时间复杂度为$O(mlog(n))$,空间复杂度为$O(1)$**,其中m为房屋个数,n为供暖器个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def findRadius(self, houses, heaters):
"""
:type houses: List[int]
:type heaters: List[int]
:rtype: int
"""
heaters.append(float('inf'))
heaters.append(-float('inf'))
heaters.sort()
max_dis = 0
for h in houses:
left, right = 0, len(heaters)
while left < right:
mid = (left + right) // 2
if heaters[mid] >= h:
right = mid
else:
left = mid + 1
max_dis = max(max_dis, min(h - heaters[left - 1], heaters[left] - h))
return max_dis

刷题总结

  这个题目难度不大,但是往往第一眼看上去并没有思路,小伙伴们需要多见一些题目,这样才能迅速反应过来如何求解。

-------------本文结束感谢您的阅读-------------
0%