数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找最近的房间
假设有一个名为`rooms`的数组，其中`rooms[i]`包含一个对[`roomId_i`, `size_i`]，表示一个ID为`roomId_i`，大小为`size_i`的房间。所有房间号都是不同的。我们还有一个`queries`数组，其中`queries[j]`包含一个对[`preferred_j`, `minSize_j`]。第j个查询的答案是一个房间的房间号ID，满足以下条件：
房间的大小至少为`minSize_j`，并且
|id - preferred_j|最小化。
如果绝对差值相同，则使用ID最小的房间。如果没有这样的房间，则返回-1。因此，我们必须找到一个名为`answer`的数组，其长度与`queries`相同，其中包含第j个查询的答案。
因此，如果输入类似于`rooms = [[2,2],[1,2],[3,2]] queries = [[3,1],[3,3],[5,2]]`，则输出将为`[3, -1, 3]`，因为：
对于查询[3,1]：房间3是最接近的，因为|3 - 3| = 0，其大小2至少为1，所以答案是3。
对于查询[3,3]：没有大小至少为3的房间，所以答案是-1。
对于查询[5,2]：房间3是最接近的，因为|3 - 5| = 2，其大小2至少为2，所以答案是3。
为了解决这个问题，我们将遵循以下步骤：
根据大小对`rooms`进行排序，如果大小相同，则根据房间ID排序。
queries = 一个由三元组(qid,size,i)组成的列表，其中i为索引，(qid, size)为queries中的对。
根据大小反向排序`queries`，如果大小相同，则根据`preferred`排序，如果两者都相同，则根据索引排序。
ans := 一个与queries大小相同的数组，并用-1填充。
X := 一个新的列表。
对于`queries`中的每个(qid, size, i)，执行以下操作：
当`rooms`不为空且`rooms`的最后一个元素的大小>= size时，执行以下操作：
(idr, p) := 从`rooms`中删除最后一个元素。
插入idr后对X进行排序。
如果X不为空，则：
j := 将qid插入X以保持X排序的索引。
如果j等于X的大小，则：
ans[i] := X的最后一个元素。
否则，如果j等于0，则：
ans[i] := X[0]
否则：
如果X[j] - qid < qid - X[j-1]，则：
ans[i] := X[j]
否则：
ans[i] := X[j-1]
返回ans。
示例
让我们看看下面的实现以更好地理解。
import bisect
def solve(rooms, queries):
rooms.sort(key = lambda x: (x[1], x[0]))
queries = [(qid,size,i) for i, (qid, size) in enumerate(queries)]
queries.sort(key = lambda x: (x[1], x[0], x[2]), reverse = True)
ans = [-1] * len(queries)
X = []
for qid, size, i in queries:
while rooms and rooms[-1][1] >= size:
idr, _ = rooms.pop()
bisect.insort(X, idr)
if X:
j = bisect.bisect(X, qid)
if j == len(X):
ans[i] = X[-1]
elif j == 0:
ans[i] = X[0]
else:
if X[j] - qid < qid - X[j-1]:
ans[i] = X[j]
else:
ans[i] = X[j-1]
return ans
rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries))输入
[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]
输出
[3, -1, 3]
浏览量：137
