当前位置：首页 > news >正文

网站建设及报价方案/推广app的平台

news 文章来源：https://blog.csdn.net/he_zhidan/article/details/134992262 2025/3/14 3:51:47

网站建设及报价方案,推广app的平台,台州企业网站seo,江油市建设局网站本文涉及的基础知识点二分查找算法合集题目给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] [xi, yi] 。对于第 i 个查询，在所有满足 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 <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹
1 <= queries.length <= 10⁵
queries[i].length == 2
xi == queries[i][1]
yi == queries[i][2]
1 <= xi, yi <= 10⁹

离线查询、值降序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，由于值是降序，所有第一个值就是答案。

代码

核心代码

template<class _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:template<class _Pr1, class _Pr2>void 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;}template<class _Pr1, class _Pr2>void 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:vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {vector<int> 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_queue<pair<int, int>> maxHeap;for (int i = 0; i < nums1.size(); i++){maxHeap.emplace(nums1[i], nums2[i]);}COrderValueMap<int, int, false, true> ySum;vector<int> 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;}
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> nums1, nums2;vector<vector<int>> 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(vector<int>{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(vector<int>{9, 9, 9}, res);}{Solution slu;nums1 = { 2,1 }, nums2 = { 2,3 }, queries = { {3,3} };auto res = slu.maximumSumQueries(nums1, nums2, queries);Assert(vector<int>{-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_map<int,int> m_mData;
};

class Solution {
public:
vector maximumSumQueries(vector& nums1, vector& nums2, vector<vector>& 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 int&i1, const int& i2)
{
return queries[i1][1] > queries[i2][1];
});
std::multimap<int, std::pair<int, 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(iMaxValue+1);
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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。