【LeetCode】供暖器 （附sort、bisect函数整理）

【LeetCode】供暖器 （附sort、bisect函数整理） 题目描述

475.冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

示例

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

输入：houses = [1,5], heaters = [2]
输出：3

方法

排序和二分查找：
首先对供暖器进行排序，然后利用二分查找分别查找每个房间对应的最近的热水器的左右距离（找最小）。最后返回最大的供热半径，即为可以覆盖所有房屋的最小加热半径。
特别地，对于下标的处理，若超出供暖器的范围则返回无穷大。

Python 函数整理

• sort（）
  函数 sort()用于列表中元素的排序（默认升序排序）

• bisect_right ()
  Python的列表(list)类型内部是一个线性表，在线性表中查找元素复杂度为O(N)，即调用list.index()的复杂的是O(N)。当数据量较大时，应该使用二分查找优化，二分查找范围每次缩小一般，复杂度为log(N)，数据量越大速度差距越明显。

bisect模块就是基于二分实现的，二分查找要求列表是有序的 ，bisect实现了在一个有序列表中①插入元素并保持列表为有序状态、或②返回插入位置但并不进行实际的插入。

bisect一共有6个函数：[‘bisect’, ‘bisect_left’, ‘bisect_right’, ‘insort’, ‘insort_left’, ‘insort_right’]，使用这些函数前要确保 *** 作的列表是有序的 。

bisect_left 和 bisect_right 函数，用入处理将会插入重复数值的情况，返回将会插入的位置。
参考文章

• if 语句写一行的含义

right_radius = heaters[j] - house if j < len(heaters) else float('inf')

满足 if 语句返回if前面的值，否则返回else后面的值。

总代码

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        max_radius = 0
        heaters.sort()
        for house in houses:
            j = bisect_right(heaters, house)
            i = j - 1
            right_radius = heaters[j] - house if j < len(heaters) else float('inf')
            left_radius = house - heaters[i] if i >= 0 else float('inf')
            min_radius = min(right_radius, left_radius)
            max_radius = max(max_radius, min_radius)
        return max_radius

时间复杂度：O((n + m) log n）