相关专题
二分查找相关题目
题目
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
参数范围:
1 -109 nums1 和 nums2 均为升序排列
1
分析
本题还可以用多路归并。
时间复杂度
O(log(m)*o(n2))+O(k+n1)。m是nums1和nums2的最大值。n1是nums1的长度,n2是nums2的长度。
步骤
一,二分找到和第k小的数对的和right。
二,收集所有和小于right的数对,和等于right的数对只收集llEqualNum 对,GetLessEqualNum(nums1, nums2, right – 1)是少于right的数对数量。
GetLessEqualNum
此函数的作用:求和小于等于iSum数对数量。
std::upper_bound(nums2.begin(), nums2.end(), iSum – n)- nums2.begin(); 是数对(n,?) 之和小于等于iSum的数量。
注意: 返回值可能是1e10,超过int的返回,所以返回值用long long。
和第k小的数对的和
第一个符合以下的要求的iSum(符合要求的最小iSum) ,和小于等于iSum的数对数量大于等于k。
代码
核心代码
class Solution {
publ服务器托管网ic:
vectorvectorint>> kSmallestPairs(vectorint>& nums1, vectorint>& nums2, int k) {
int left = nums1[0] + nums2[0] - 1, right = nums1.back() + nums2.back();
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
if (GetLessEqualNum(nums1, nums2, mid) >= k)
{
right = mid;
}
else
{
left = mid;
}
}
lon服务器托管网g long llEqualNum = k - GetLessEqualNum(nums1, nums2, right - 1);
vectorvectorint>> vRet;
for (const auto& n : nums1)
{
for (const auto n2 : nums2)
{
if (n + n2 right)
{
vRet.emplace_back(vectorint>{n, n2});
}
else if ((n + n2 == right)&&(llEqualNum))
{
llEqualNum--;
vRet.emplace_back(vectorint>{n, n2});
}
else
{
break;
}
}
}
return vRet;
}
long long GetLessEqualNum(const vectorint>& nums1, const vectorint>& nums2, int iSum)
{
long long llNum = 0;
for (const auto& n : nums1)
{
llNum += std::upper_bound(nums2.begin(), nums2.end(), iSum - n)- nums2.begin();
}
return llNum;
}
};
测试代码
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 {
Assert(v1[i], v2[i]);
}
}
int main()
{
vector nums1, nums2;
int k;
vector res;
{
Solution slu;
nums1 = { -10,-4,0,0,6 }, nums2 = { 3,5,6,7,8,100 };
k = 10;
res = slu.kSmallestPairs(nums1, nums2, k);
Assert(vector{ { {-10, 3}, { -10,5 }, { -10,6 }, { -10,7 }, { -10,8 }, { -4,3 }, { -4,5 }, { -4,6 }, { 0,3 }, { 0,3 }}}, res);
}
{
Solution slu;
nums1 = { 1,7,11 }, nums2 = { 2,4,6 };
k = 3;
res = slu.kSmallestPairs(nums1,nums2, k);
Assert(vector{ {1, 2}, { 1,4 }, { 1,6 }}, res);
}
{
Solution slu;
nums1 = { 1,1,2 }, nums2 = { 1,2,3 };
k = 2;
res = slu.kSmallestPairs(nums1, nums2, k);
Assert(vector{ {1, 1}, { 1,1 }}, res);
}
{
Solution slu;
nums1 = { 1,2 }, nums2 = { 3 };
k = 3;
res = slu.kSmallestPairs(nums1, nums2, k);
Assert(vector{ {1, 3}, { 2,3 }}, 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
洒家想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
墨家名称的来源:有所得以墨记之。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:
VS2022 C++17
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: 坚守数字化创新烽火之地 百望云入选新华社“品牌信用建设典型案例”
潮起海之南,风好正扬帆。2023年12月2日-5日,南海之滨,由新华通讯社、海南省人民政府、中国品牌建设促进会主办的主题为“聚焦新质生产力,增强发展新动能”的2023中国企业家博鳌论坛在海南博鳌隆重举行。 群贤毕至,高朋满座——百望云接受新华社邀请,与众多世界…