苏州网站开发建设方法,现在ps做网站的尺寸,岳阳seo官网,专业网站建设服务公司哪家好本文涉及的基础知识点
二分查找算法合集
题目
给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 #xff0c;另给你一个下标从 1 开始的二维数组 queries #xff0c;其中 queries[i] [xi, yi] 。 对于第 i 个查询#xff0c;在所有满足 nums1[j] xi 且…本文涉及的基础知识点
二分查找算法合集
题目
给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 另给你一个下标从 1 开始的二维数组 queries 其中 queries[i] [xi, yi] 。 对于第 i 个查询在所有满足 nums1[j] xi 且 nums2[j] yi 的下标 j (0 j n) 中找出 nums1[j] nums2[j] 的 最大值 如果不存在满足条件的 j 则返回 -1 。 返回数组 answer 其中 answer[i] 是第 i 个查询的答案。 示例 1 输入nums1 [4,3,1,2], nums2 [2,4,9,5], queries [[4,1],[1,3],[2,5]] 输出[6,10,7] 解释 对于第 1 个查询xi 4 且 yi 1 可以选择下标 j 0 此时 nums1[j] 4 且 nums2[j] 1 。nums1[j] nums2[j] 等于 6 可以证明 6 是可以获得的最大值。 对于第 2 个查询xi 1 且 yi 3 可以选择下标 j 2 此时 nums1[j] 1 且 nums2[j] 3 。nums1[j] nums2[j] 等于 10 可以证明 10 是可以获得的最大值。 对于第 3 个查询xi 2 且 yi 5 可以选择下标 j 3 此时 nums1[j] 2 且 nums2[j] 5 。nums1[j] nums2[j] 等于 7 可以证明 7 是可以获得的最大值。 因此我们返回 [6,10,7] 。 示例 2 输入nums1 [3,2,5], nums2 [2,3,4], queries [[4,4],[3,2],[1,1]] 输出[9,9,9] 解释对于这个示例我们可以选择下标 j 2 该下标可以满足每个查询的限制。 示例 3 输入nums1 [2,1], nums2 [2,3], queries [[3,3]] 输出[-1] 解释示例中的查询 xi 3 且 yi 3 。对于每个下标 j 都只满足 nums1[j] xi 或者 nums2[j] yi 。因此不存在答案。 参数范围 nums1.length nums2.length n nums1.length 1 n 105 1 nums1[i], nums2[i] 109 1 queries.length 105 queries[i].length 2 xi queries[i][1] yi queries[i][2] 1 xi, yi 109
离线查询、值降序map
时间复杂度nlogn)。 按xi的降序对queries的索引排序。
变量解析
maxHeap记录所有的nums1[j]和nums2[j]nums1[j]大的在堆顶ySum记录所有nums[j]大于当前xi的nums2[j]和nums1[j]nums2[j]键升序值降序。如果 nums2[j1] nums2[j2]且nums1[j1]nums2[j1] nums1[j2]nums2[j2]。则j1被j2淘汰了。it[it,ySum.m_map.end()) 中的元素全部大于xi和yi由于值是降序所有第一个值就是答案。
代码
核心代码
templateclass _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey
class COrderValueMap
{
public:void Add (_Kty key, _Ty value){if (bOutSmallKey){if (bValueDdes){AddOutSmall(key, value, std::less_equal_Ty(), std::greater_equal_Ty());}else{AddOutSmall(key, value, std::greater_equal_Ty(), std::less_equal_Ty());}}else {if (bValueDdes){AddNotOutSmall(key, value, std::greater_equal_Ty(), std::less_equal_Ty());}else{AddNotOutSmall(key, value, std::less_equal_Ty(), std::greater_equal_Ty());}}};std::map_Kty, _Ty m_map;
protected:templateclass _Pr1, class _Pr2void AddOutSmall(_Kty key, _Ty value, _Pr1 pr1, _Pr2 pr2){auto it m_map.lower_bound(key);if ((m_map.end() ! it) pr1(it-second, value)){return;//被旧值淘汰}auto ij it;while (it ! m_map.begin()){--it;if (pr2(it-second, value)){it m_map.erase(it);}}m_map[key] value;}templateclass _Pr1, class _Pr2void AddNotOutSmall(_Kty key, _Ty value, _Pr1 pr1,_Pr2 pr2 ){auto it m_map.upper_bound(key);if ((m_map.begin() ! it) pr1(std::prev(it)-second, value)){return;//被淘汰}auto ij it;for (; (m_map.end() ! ij) pr2(ij-second, value); ij);m_map.erase(it, ij);m_map[key] value;};};class Solution {
public:vectorint maximumSumQueries(vectorint nums1, vectorint nums2, vectorvectorint queries) {vectorint indexs(queries.size());iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [](const int i1, const int i2) {return queries[i1][0] queries[i2][0]; });priority_queuepairint, int maxHeap;for (int i 0; i nums1.size(); i){maxHeap.emplace(nums1[i], nums2[i]);}COrderValueMapint, int, false, true ySum;vectorint vRet(queries.size(), -1);for (const auto i : indexs){while (maxHeap.size() (maxHeap.top().first queries[i][0])){ySum.Add(maxHeap.top().second, maxHeap.top().first maxHeap.top().second);maxHeap.pop();}auto it ySum.m_map.lower_bound(queries[i][1]);if (ySum.m_map.end() ! it){vRet[i] it-second;}}return vRet;}
};测试用例
templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorint nums1, nums2;vectorvectorint queries;{Solution slu; nums1 { 4,3,1,2 }, nums2 { 2,4,9,5 }, queries { {4,1},{1,3},{2,5} };auto res slu.maximumSumQueries(nums1,nums2,queries);Assert(vectorint{6, 10, 7}, res);}{Solution slu;nums1 { 3,2,5 }, nums2 { 2,3,4 }, queries { {4,4},{3,2},{1,1} };auto res slu.maximumSumQueries(nums1, nums2, queries);Assert(vectorint{9, 9, 9}, res);}{Solution slu;nums1 { 2,1 }, nums2 { 2,3 }, queries { {3,3} };auto res slu.maximumSumQueries(nums1, nums2, queries);Assert(vectorint{-1}, res);}
}2023年6月代码
class CMaxLineTreeMap { public: CMaxLineTreeMap(int iArrSize) :m_iArrSize(iArrSize) { } //iIndex 从0开始 void Modify(int iIndex, int iValue) { Modify(1, 1, m_iArrSize, iIndex 1, iValue); } //iNeedQueryLeft iNeedQueryRight 从0开始 int Query(const int iNeedQueryLeft, const int iNeedQueryRight) { return Query(1, 1, m_iArrSize, iNeedQueryLeft 1, iNeedQueryRight 1); } protected: int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight) { if ((iNeedQueryLeft iRecordLeft) (iNeedQueryRight iRecordRight)) { return m_mData[iTreeNodeIndex]; } const int iMid (iRecordLeft iRecordRight) / 2; int iRet 0; if (iNeedQueryLeft iMid) { iRet Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight); } if (iNeedQueryRight iMid) { iRet max(iRet, Query(iTreeNodeIndex * 2 1, iMid 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight)); } return iRet; } void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue) { if (iLeft iRight) { m_mData[iTreeNodeIndex] max(m_mData[iTreeNodeIndex],iValue); return; } const int iMid (iLeft iRight) / 2; if (iIndex iMid) { Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue); } else { Modify(iTreeNodeIndex * 2 1, iMid 1, iRight, iIndex, iValue); } m_mData[iTreeNodeIndex] max(m_mData[iTreeNodeIndex * 2], m_mData[iTreeNodeIndex * 2 1]); } const int m_iArrSize; std::unordered_mapint,int m_mData; };
class Solution { public: vector maximumSumQueries(vector nums1, vector nums2, vectorvector queries) { m_c queries.size(); vector indexs; for (int i 0; i m_c; i) { indexs.emplace_back(i); } std::sort(indexs.begin(), indexs.end(), [queries](const inti1, const int i2) { return queries[i1][1] queries[i2][1]; }); std::multimapint, std::pairint, int m_Num2ToNum1Sum; for (int i 0; i nums2.size(); i) { m_Num2ToNum1Sum.emplace(nums2[i], std::make_pair(nums1[i], nums1[i] nums2[i])); } vector vRet(m_c); auto it m_Num2ToNum1Sum.rbegin(); const int iMaxValue 1000 * 1000 * 1000; CMaxLineTreeMap lineTree(iMaxValue1); for (int index 0; index indexs.size(); index) { const int i indexs[index]; const auto que queries[i]; while ((it ! m_Num2ToNum1Sum.rend()) (it-first que[1])) { lineTree.Modify(it-second.first, it-second.second); it; } vRet[i] lineTree.Query(que[0], iMaxValue); if (0 vRet[i]) { vRet[i] -1; } } return vRet; } int m_c; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
