最近的房间

标签: 数组 二分查找 排序

难度: Hard

一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。

同时给你 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferredj, minSizej] 。第 j 个查询的答案是满足如下条件的房间 id ：

  • 房间的面积 至少 为 minSizej ，且
  • abs(id - preferredj) 的值 最小 ，其中 abs(x) 是 x 的绝对值。

如果差的绝对值有 相等 的，选择 最小 的 id 。如果 没有满足条件的房间 ，答案为 -1 。

请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。

 

示例 1：

输入：rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
输出：[3,-1,3]
解释：查询的答案如下：
查询 [3,1] ：房间 3 的面积为 2 ，大于等于 1 ，且号码是最接近 3 的，为 abs(3 - 3) = 0 ，所以答案为 3 。
查询 [3,3] ：没有房间的面积至少为 3 ，所以答案为 -1 。
查询 [5,2] ：房间 3 的面积为 2 ，大于等于 2 ，且号码是最接近 5 的，为 abs(3 - 5) = 2 ，所以答案为 3 。

示例 2：

输入：rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
输出：[2,1,3]
解释：查询的答案如下：
查询 [2,3] ：房间 2 的面积为 3 ，大于等于 3 ，且号码是最接近的，为 abs(2 - 2) = 0 ，所以答案为 2 。
查询 [2,4] ：房间 1 和 3 的面积都至少为 4 ，答案为 1 因为它房间编号更小。
查询 [2,5] ：房间 3 是唯一面积大于等于 5 的，所以答案为 3 。

 

提示：

  • n == rooms.length
  • 1 <= n <= 105
  • k == queries.length
  • 1 <= k <= 104
  • 1 <= roomIdi, preferredj <= 107
  • 1 <= sizei, minSizej <= 107

Submission

运行时间: 236 ms

内存: 53.5 MB

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        # 获取rooms和queries的数组大小
        m,n=len(rooms),len(queries)
        # 将rooms和queries按照size从大到小排序
        rooms.sort(key=lambda x:x[1],reverse=True)
        index=sorted(range(n),key=lambda i:queries[i][1],reverse=True)
        # ids用于存储当前大于minSize的房间的id
        ids=[]
        # 遍历rooms的索引
        j=0
        # 返回值
        res=[-1]*n

        for i in index:
            preferred,minSize=queries[i]
            # 二分插入大于等于minSize的id
            while j<m and rooms[j][1]>=minSize:
                bisect.insort(ids,rooms[j][0])
                j+=1
            # 如果没有大于等于minSize的房间，res的结果为-1，continue
            if not ids:
                continue
            # 二分查找ids中大于等于preferred的索引
            k=bisect.bisect_left(ids,preferred) 
            # 对边界处理
            if k==0:
                res[i]=ids[0]
            elif k==len(ids):
                res[i]=ids[-1]
            else:
                # 非边界处理
                if abs(ids[k]-preferred)<abs(ids[k-1]-preferred):
                    res[i]=ids[k]
                else:
                    res[i]=ids[k-1]

        return res

Explain

本题解采用排序和二分查找的方法。首先，将房间按照面积从大到小排序，将查询按照最小面积从大到小排序。然后，遍历查询，对于每个查询，使用二分查找在已经满足面积要求的房间中找到最接近期望房间号的房间。具体而言，先二分插入所有满足面积要求的房间号，然后二分查找找到最接近期望房间号的房间。

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

空间复杂度: O(m + n)

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        m, n = len(rooms), len(queries)
        rooms.sort(key=lambda x: x[1], reverse=True)
        index = sorted(range(n), key=lambda i: queries[i][1], reverse=True)
        ids = []
        j = 0
        res = [-1] * n

        for i in index:
            preferred, minSize = queries[i]
            while j < m and rooms[j][1] >= minSize:
                bisect.insort(ids, rooms[j][0])
                j += 1
            if not ids:
                continue
            k = bisect.bisect_left(ids, preferred)
            if k == 0:
                res[i] = ids[0]
            elif k == len(ids):
                res[i] = ids[-1]
            else:
                if abs(ids[k] - preferred) < abs(ids[k - 1] - preferred):
                    res[i] = ids[k]
                else:
                    res[i] = ids[k - 1]

        return res

Explore

按面积从大到小排序房间是为了在处理查询时更高效地满足面积要求。这种排序方式使得在遍历查询时，可以从最大面积的房间开始添加到可选择列表中，确保一旦房间被添加，所有后续的查询（由于也是按面积要求从大到小排序）都不需要重新检查这些已添加的房间。这样可以避免重复工作，提高整体查询效率。

查询排序的目的是按照面积需求从大到小对查询进行排序，这样可以确保处理较大面积需求的查询时，已经考虑了所有可能的房间选项。这样的排序配合房间的排序，使得在遍历过程中可以持续维护一个当前符合面积条件的房间列表，而不需要为每个查询重新计算符合条件的房间列表，从而优化整体的查找效率。

当存在多个房间号与预期房间号的距离相等时，算法会选择最小的那个房间号。具体实现为，如果二分查找的结果k在已有房间列表中，且k和k-1两个位置的房间号与预期房间号的距离相同，那么选择两者中较小的房间号。这样的处理确保了在距离相等的情况下，结果具有一致的选择偏好，即偏向于房间号较小的选项。

当`bisect.bisect_left`返回的索引`k`为0时，意味着所有可选房间的编号都大于预期的房间编号，因此直接选择列表中最小的编号（即`ids[0]`）为最接近的选择。相反，当`k`等于`ids`的长度时，表示所有可选房间的编号都小于预期的房间编号，因此直接选择列表中最大的编号（即`ids[-1]`）为最接近的选择。这种处理方式确保了在极端情况下能够提供一个有效且逻辑上合理的选项。