当前位置：首页 > article >正文

Leetcode1847：最近的房间

article 2025/1/31 13:52:50

题目描述：

一个酒店里有 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 个查询的结果。

代码思路：

房间排序：
- 首先，对房间列表 rooms 按照房间大小从大到小进行排序。这是因为如果房间越大，它越有可能满足更多的查询（因为查询要求的是最小房间大小）。
查询预处理：
- 给每个查询添加一个索引 i，以便在结果列表 res 中正确放置答案。
- 然后，根据查询的最小房间大小从大到小对查询进行排序。这样做是为了保证在处理查询时，可以逐步增加符合条件的房间（因为房间已经按大小从大到小排序），从而避免重复处理。
初始化结果和辅助数据结构：
- 初始化结果列表 res，其长度为查询的数量，初始值为 0（后续会被替换为房间号或 -1）。
- 使用一个哨兵值 INF（这里设为 10 ** 9），用于在 SortedSet 中表示无穷大，确保所有查询都能被正确处理（即使偏好房间号大于所有房间号或小于所有房间号）。
- 初始化一个 SortedSet（有序集合），并添加 -INF 和 INF 作为边界，确保可以在集合中找到合适的插入位置。
滑动窗口和查询处理：
- 使用一个指针 ri 来遍历房间列表，并维护一个 SortedSet window 来存储当前可能满足查询条件的房间号。
- 对于每个查询，逐步将满足最小房间大小的房间号加入 window，直到 window 中的房间不再满足查询的最小房间大小要求。
- 使用 SortedSet 的 bisect_left 方法找到查询偏好房间号在 window 中的插入位置 idxR，以及它的前一个位置 idxL。
- 比较偏好房间号与 idxL 和 idxR 对应的房间号的距离，选择距离最小的房间号作为结果。
- 如果结果是 -INF 或 INF，表示没有找到合适的房间，将结果设置为 -1。
返回结果：
- 最后，返回结果列表 res，其中包含了每个查询的最近房间号或 -1

代码实现：

from sortedcontainers import SortedSet
class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        rooms.sort(key = lambda r: -r[1])   #按照size从大到小排序
        rn = len(rooms)
    
        qn = len(queries)
        for i in range(qn):
            queries[i].append(i)        #加上index。在进res时按照index放置
        queries.sort(key = lambda q: -q[1]) #按照minSize从大到小排列
        
        res = [0 for _ in range(qn)]
        INF = 10 ** 9   #哨兵
        window = SortedSet()
        window.add(-INF)
        window.add(INF)
        ri = 0
        for preferID, minSize, qID in queries:
            while ri < rn and rooms[ri][1] >= minSize:  #房间的size比minSize大
                window.add(rooms[ri][0])     #房间号入window 
                ri += 1
            idxR = window.bisect_left(preferID)
            idxL = idxR - 1
            L, R = window[idxL] , window[idxR]
            res[qID] = L if (preferID - L) <= (R - preferID) else R
            if res[qID] in (-INF, INF):
                res[qID] = -1
        return res

查看全文

http://www.kler.cn/a/441245.html