江苏工信部网站备案查询,美业管理软件系统排名,网站建设的法律依据,外包网络推广公司怎么选本文涉及的基础知识点
二分查找算法合集 离线查询
题目
给你一个下标从 0 开始的正整数数组 heights #xff0c;其中 heights[i] 表示第 i 栋建筑的高度。 如果一个人在建筑 i #xff0c;且存在 i j 的建筑 j 满足 heights[i] heights[j] #xff0c;那么这个…本文涉及的基础知识点
二分查找算法合集 离线查询
题目
给你一个下标从 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那说明i1i2,i2i3也就是i1i3那直接跳到i3就可以了。 三种情况
两人都不跳初始位置相同一人直接跳到另外一个人处两个人都跳
两个人都跳
假定两人的最大位置是iMaxIndex两人的最大高度是iMaxHeight。heights(iMaxIndex…]中寻找大于iMaxHeight的组合 如果存在多个组合返回最小的索引。 mHeightIndexs的key是高度value是索引。如果key1 key0且value1 value0那key0被淘汰。 淘汰后key和value都升序。
离线查询
如果iMaxIndex是按降序排列那么mHeightIndexs每个元素只需要插入一次。
代码
核心代码
class Solution { public: vector leftmostBuildingQueries(vector heights, vectorvector 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]); }); COrderValueMapint,int,true,true 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; vectorvector 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);}
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。墨子曰事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
