首页 > 学院 > 开发设计 > 正文

475. Heaters

2019-11-08 03:09:01
字体:
来源:转载
供稿:网友

该题目简而言之,就是找出每个house的min heater(距离最近的heater),算出radius(半径),再找出所有house对应的radius中的最大值,即为标准供热半径。

binary search可以找出有序数组中需要查找的数字

简单举例: houses[14] heaters[1,8,10,20,32] 只有一间屋子,位于14这个位置,左侧最近的heater位于10,右侧最近的heater位于20,min(14-10,20,14)=4,所以14这件屋子需要供热的话,radius=4即可 (这是最基本的思路)

下述算法给出的是对基本算法略微改进的算法,希望读者在基本思路的基础上去理解下述算法。


class Solution(object): def findRadius(self, houses, heaters): """ :type houses: List[int] :type heaters: List[int] :rtype: int """ heaters = sorted(heaters) houses = sorted(houses) i = radius = 0 for house in houses: while i < len(heaters) - 1 and house > heaters[i]: i += 1 if i != 0: radius = max(radius, min(house - heaters[i - 1],abs(house - heaters[i]))) else: radius = max(abs(house - heaters[0]), radius) return radius
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表