資料結構
網路
關係資料庫管理系統 (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
