相關(guān)專題

二分查找相關(guān)題目

題目

給定兩個以 非遞減順序排列 的整數(shù)數(shù)組 nums1 和 nums2 , 以及一個整數(shù) k 。
定義一對值 (u,v)，其中第一個元素來自 nums1，第二個元素來自 nums2 。
請找到和最小的 k 個數(shù)對 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1:
輸入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
輸出: [1,2],[1,4],[1,6]
解釋: 返回序列中的前 3 對數(shù)：
[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 對數(shù)：
[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]
解釋: 也可能序列中所有的數(shù)對都被返回:[1,3],[2,3]
參數(shù)范圍:
1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均為升序排列
1 <= k <= 104

分析

本題還可以用多路歸并。

時間復(fù)雜度

O(log(m)*o(n2))+O(k+n1)。m是nums1和nums2的最大值。n1是nums1的長度,n2是nums2的長度。

步驟

一，二分找到和第k小的數(shù)對的和right。
二，收集所有和小于right的數(shù)對，和等于right的數(shù)對只收集llEqualNum 對，GetLessEqualNum(nums1, nums2, right - 1)是少于right的數(shù)對數(shù)量。

GetLessEqualNum

此函數(shù)的作用：求和小于等于iSum數(shù)對數(shù)量。
std::upper_bound(nums2.begin(), nums2.end(), iSum - n)- nums2.begin(); 是數(shù)對(n,?) 之和小于等于iSum的數(shù)量。
注意: 返回值可能是1e10，超過int的返回，所以返回值用long long。

和第k小的數(shù)對的和

第一個符合以下的要求的iSum（符合要求的最小iSum) ，和小于等于iSum的數(shù)對數(shù)量大于等于k。

代碼

核心代碼

class Solution {
public:vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& 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;}}long long llEqualNum = k - GetLessEqualNum(nums1, nums2, right - 1);vector<vector<int>> vRet;for (const auto& n : nums1){for (const auto n2 : nums2){if (n + n2 < right){vRet.emplace_back(vector<int>{n, n2});}else if ((n + n2 == right)&&(llEqualNum)){llEqualNum--;vRet.emplace_back(vector<int>{n, n2});}else{break;}}}return vRet;}long long GetLessEqualNum(const vector<int>& nums1, const vector<int>& 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 < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
vector nums1, nums2;
int k;
vector<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<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<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<vector>{ {1, 1}, { 1,1 }}, res);
}
{
Solution slu;
nums1 = { 1,2 }, nums2 = { 3 };
k = 3;
res = slu.kSmallestPairs(nums1, nums2, k);
Assert(vector<vector>{ {1, 3}, { 2,3 }}, res);
}

//CConsole::Out(res);

}

擴展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標 及時的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡單的課程，請移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請下載《聞缺陷則喜算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

灑家想對大家說的話
聞缺陷則喜是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。
墨家名稱的來源：有所得以墨記之。
如果程序是一條龍，那算法就是他的是睛

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境：

VS2022 C++17