【Leetcode 每日一题】1847. 最近的房间
问题背景
一个酒店里有
n
n
n 个房间，这些房间用二维整数数组
r
o
o
m
s
rooms
rooms 表示，其中
r
o
o
m
s
[
i
]
=
[
r
o
o
m
I
d
i
,
s
i
z
e
i
]
rooms[i] = [roomId_i, size_i]
rooms[i]=[roomIdi,sizei] 表示有一个房间号为
r
o
o
m
I
d
i
roomId_i
roomIdi 的房间且它的面积为
s
i
z
e
i
size_i
sizei。每一个房间号
r
o
o
m
I
d
i
roomId_i
roomIdi 保证是 独一无二 的。
同时给你
k
k
k 个查询，用二维数组
q
u
e
r
i
e
s
queries
queries 表示，其中
q
u
e
r
i
e
s
[
j
]
=
[
p
r
e
f
e
r
r
e
d
j
,
m
i
n
S
i
z
e
j
]
queries[j] = [preferred_j, minSize_j]
queries[j]=[preferredj,minSizej]。第
j
j
j 个查询的答案是满足如下条件的房间
i
d
id
id：
房间的面积 至少 为
m
i
n
S
i
z
e
j
minSize_j
minSizej，且
- a b s ( i d − p r e f e r r e d j ) abs(id - preferred_j) abs(id−preferredj) 的值 最小 ，其中 a b s ( x ) abs(x) abs(x) 是 x x x 的绝对值。
- 如果差的绝对值有 相等 的，选择 最小 的 i d id id。如果 没有满足条件的房间 ，答案为 − 1 -1 −1。
- 请你返回长度为 k k k 的数组 a n s w e r answer answer，其中 a n s w e r [ j ] answer[j] answer[j] 为第 j j j 个查询的结果。
数据约束
- n = r o o m s . l e n g t h n = rooms.length n=rooms.length
- 1 ≤ n ≤ 1 0 5 1 \le n \le 10 ^ 5 1≤n≤105
- k = q u e r i e s . l e n g t h k = queries.length k=queries.length
- 1 ≤ k ≤ 1 0 4 1 \le k \le 10 ^ 4 1≤k≤104
- 1 ≤ r o o m I d i , p r e f e r r e d j ≤ 1 0 7 1 \le roomId_i, preferred_j \le 10 ^ 7 1≤roomIdi,preferredj≤107
- 1 ≤ s i z e i , m i n S i z e j ≤ 1 0 7 1 \le size_i, minSize_j \le 10 ^ 7 1≤sizei,minSizej≤107
解题过程
这题的暴力做法是根据每个查询的条件，依次到
r
o
o
m
s
rooms
rooms 数组中去检索，这样时间复杂度的量级大致是两个数组长度的乘积。
考虑到其中一个筛选条件是面积至少为
s
i
z
e
i
size_i
sizei，那么如果先对
r
o
o
m
s
rooms
rooms 数组从大到小排序，再维护一个有序集合，让它从大到小加入所需的答案，就可以保证维护的结果集是增量扩大的，避免重复在全局范围内搜索。
能够这样做的前提，是循环的过程中已经获取到了全部的输入数据。这种方案就叫离线，等待输入全部完成之后再处理才能够保证算法的正确性。
这时候我们会希望查询
q
u
e
r
i
e
s
queries
queries 根据查询面积的从大到小来输入，但是结果要求按
q
u
e
r
i
e
s
queries
queries 的输入顺序给定相应的输出，所以不能排序。退而求其次，构造它对应的下标数组并排序，对查询的面积大小不作要求，维护好增量扩大的结果集即可。
主要的性能瓶颈在排序和维护有序数组上，对
r
o
o
m
s
rooms
rooms 数组
q
u
e
r
i
e
s
queries
queries 数组都需要
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN) 这个水平的时间，最终的总耗时大概是根据两者的长度得到的这个级别的时间复杂度之和。
具体实现
class Solution {
public int[] closestRoom(int[][] rooms, int[][] queries) {
// 对 rooms 数组根据面积进行排序
Arrays.sort(rooms, (o1, o2) -> o2[1] - o1[1]);
int n = queries.length;
// 构造 queries 对应的下标数组，可以避免每次都在全局范围内搜索
Integer[] queryIds = new Integer[n];
Arrays.setAll(queryIds, i -> i);
// 对下标数组根据查询的面积大小进行排序
Arrays.sort(queryIds, (i1, i2) -> queries[i2][1] - queries[i1][1]);
int[] res = new int[n];
Arrays.fill(res, -1);
// 定义有序集合，在流程中增量扩大
TreeSet<Integer> roomIds = new TreeSet<>();
int j = 0;
for(int i : queryIds) {
int preferredId = queries[i][0];
int minSize = queries[i][1];
// 由于 rooms 数组已经排过序了，依次将符合条件的情形添加到结果集中
while (j < rooms.length && rooms[j][1] >= minSize) {
roomIds.add(rooms[j][0]);
j++;
}
// 找到离待查找的 preferredId 最近的两个结果，比较差值并更新到结果数组中
int diff = Integer.MAX_VALUE;
Integer floor = roomIds.floor(preferredId);
if(floor != null) {
diff = preferredId - floor;
res[i] = floor;
}
Integer ceiling = roomIds.ceiling(preferredId);
if(ceiling != null && ceiling - preferredId < diff) {
res[i] = ceiling;
}
}
return res;
}
}