怎样建立一个公司网站,中国住房和城乡建设部网站公文,腾讯云域名交易,wordpress 森林文章目录1. 题目2. 解题1. 题目
一个酒店里有 n 个房间#xff0c;这些房间用二维整数数组 rooms 表示#xff0c;其中 rooms[i] [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。
同时给你 k 个查询这些房间用二维整数数组 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 10^5
k queries.length
1 k 10^4
1 roomIdi, preferredj 10^7
1 sizei, minSizej 10^7来源力扣LeetCode 链接https://leetcode-cn.com/problems/closest-room 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 1851. 包含每个查询的最小区间排序 离线查询 优先队列
先对所有的 rooms 排序尺寸大的先 查询 q 也是尺寸大的先查后续的查询中之前的房间尺寸都是满足要求的然后依次查询将满足尺寸的房间 id 插入 set进行 二分查找找到最接近的 id
class Solution {
public:vectorint closestRoom(vectorvectorint rooms, vectorvectorint q) {// 房间尺寸从大到小排序vectorpairint,int R(rooms.size());int k 0;for(auto r : rooms){R[k] {rooms[k][0], rooms[k][1]};k;} // vector 转 成 pair 排序不做此操作超时。。。sort(R.begin(), R.end(),[](auto a, auto b){return a.second b.second;});int n q.size();vectorint ans(n, -1);vectorint idx(n);iota(idx.begin(), idx.end(),0);sort(idx.begin(), idx.end(),[](auto a, auto b){return q[a][1] q[b][1];//查询按照大的到小的查询});setint s;int j 0, preferred, minSize, closest, minidgap;for(auto i : idx){preferred q[i][0];minSize q[i][1];while(j R.size() R[j].second minSize){ // 尺寸满足的插入 id 到 sets.insert(R[j].first);j;}closest -1;minidgap INT_MAX;auto it s.lower_bound(preferred);//二分查找if(it ! s.end()){closest *it;minidgap *it - preferred;}if(it ! s.begin()){--it;if(preferred - *it minidgap){closest *it;}}ans[i] closest;}return ans;}
};608 ms 146.7 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
