首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

C++二分查找算法:找到 Alice 和 Bob 可以相遇的建筑

  • 24-02-19 21:20
  • 3142
  • 6487
blog.csdn.net

本文涉及的基础知识点

二分查找算法合集
离线查询

题目

给你一个下标从 0 开始的正整数数组 heights ,其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i ,且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ,那么这个人可以移动到建筑 j 。
给你另外一个数组 queries ,其中 queries[i] = [ai, bi] 。第 i 个查询中,Alice 在建筑 ai ,Bob 在建筑 bi 。
请你能返回一个数组 ans ,其中 ans[i] 是第 i 个查询中,Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ,Alice 和 Bob 不能相遇,令 ans[i] 为 -1 。
示例 1:
输入:heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出:[2,5,-1,5,2]
解释:第一个查询中,Alice 和 Bob 可以移动到建筑 2 ,因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Alice 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中,Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。
示例 2:
输入:heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出:[7,6,-1,4,6]
解释:第一个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[0] < heights[7] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 6 ,因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Bob 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 4 ,因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。
参数范围:
1 <= heights.length <= 5 * 104
1 <= heights[i] <= 109
1 <= queries.length <= 5 * 104
queries[i] = [ai, bi]
0 <= ai, bi <= heights.length - 1

分析

时间复杂度

时间复杂度(nlogm),枚举queries时间复杂度O(n),处理单个查询时间复杂度O(logm)。n和queries的长度,m是heights的长度。

分情况讨论

无需考虑一个人跳两次及以上的情况。假定跳了两次: i1->i2->i3,那说明i1 三种情况:

两人都不跳,初始位置相同
一人直接跳到另外一个人处
两个人都跳

两个人都跳

假定两人的最大位置是iMaxIndex,两人的最大高度是iMaxHeight。heights(iMaxIndex…]中寻找大于iMaxHeight的组合, 如果存在多个组合,返回最小的索引。
mHeightIndexs的key是高度,value是索引。如果key1 >= key0,且value1 <= value0,那key0被淘汰。
淘汰后,key和value都升序。

离线查询

如果iMaxIndex是按降序排列,那么mHeightIndexs每个元素只需要插入一次。

代码

核心代码

class Solution {
public:
vector leftmostBuildingQueries(vector& heights, vector& queries) {
m_c = queries.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.emplace_back(i);
}
sort(indexs.begin(), indexs.end(), [&](const int& i1, const int& i2)
{
return max(queries[i1][0], queries[i1][1]) > max(queries[i2][0], queries[i2][1]);
});
COrderValueMap mHeightIndexs;
vector vRet(m_c, -1);
int iHeightIndex = heights.size() - 1;
for (int inx :indexs)
{
const int iMinIndex = min(queries[inx][0], queries[inx][1]);
const int iMaxIndex = max(queries[inx][0], queries[inx][1]);
if (iMinIndex == iMaxIndex) {
vRet[inx] = iMaxIndex;
continue;
}
if (heights[iMinIndex] < heights[iMaxIndex])
{
vRet[inx] = iMaxIndex;
continue;
}
const int iMaxHeight = max(heights[queries[inx][0]], heights[queries[inx][1]]);
while (iHeightIndex > iMaxIndex)
{
mHeightIndexs.Add(heights[iHeightIndex], iHeightIndex);
iHeightIndex–;
}
auto it = mHeightIndexs.m_map.upper_bound(iMaxHeight);
if (mHeightIndexs.m_map.end() != it)
{
vRet[inx] = it->second;
}
}
return vRet;
}
int m_c;
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vectorheights;
vector queries;
int k;
vector res;
{
Solution slu;
heights = {6, 4, 8, 5, 2, 7};
queries = { {0, 1}, { 0,3 }, { 2,4 }, { 3,4 }, { 2,2 }};
res = slu.leftmostBuildingQueries(heights, queries);
//Assert(1, res);
}

//CConsole::Out(res);
  • 1

}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨子曰:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
群中有博文配套源码
QQ群名片
注:本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/134488898"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top