本文涉及的基礎知識點
二分查找算法合集
本題的簡化
C++二分查找算法：查找和最小的 K 對數字 十分接近m恒等于2
題目
給你一個 m * n 的矩陣 mat，以及一個整數 k ，矩陣中的每一行都以非遞減的順序排列。
你可以從每一行中選出 1 個元素形成一個數組。返回所有可能數組中的第 k 個 最小 數組和。
示例 1：
輸入：mat = [[1,3,11],[2,4,6]], k = 5
輸出：7
解釋：從每一行中選出一個元素，前 k 個和最小的數組分別是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 個的和是 7 。
示例 2：
輸入：mat = [[1,3,11],[2,4,6]], k = 9
輸出：17
示例 3：
輸入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
輸出：9
解釋：從每一行中選出一個元素，前 k 個和最小的數組分別是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 個的和是 9 。
示例 4：
輸入：mat = [[1,1,10],[2,2,9]], k = 7
輸出：12
參數范圍：
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一個非遞減數組
分析
時間復雜度
O(mlog(500040)n+mkn)。GetLessKSum被調用m次，GetLessEqualSumNum共被調用mlog(500040)次。每次調用GetLessEqualSumNum，for循環共執行m次。
vRet.emplace_back極端情況下，可能被執行kn次。
主要函數介紹
| GetLessKSum | 兩行升序數據的最小k個和 |
| GetLessEqualSumNum | 兩行升序數據和小于等于iSum的組合數量 |
注意：nums[i]為正數，所以如果pre的數量大于k，只需要保留前k小，其它的被淘汰了。
二分
尋找第一個符合條件的iSum，條件如下：
和小于等于iSum的組合數量大于等于k。
代碼
核心代碼
class Solution {
public:int kthSmallest(vector<vector<int>>& mat, int k) {m_c = mat.front().size();m_iK = k;vector<int> pre = mat[0];for (int r = 1; r < mat.size(); r++){pre = GetLessKSum(pre, mat[r]);}return pre.back();}vector<int> GetLessKSum(const vector<int>& pre, const vector<int>& cur){int left = 0, right = 5000 * 40;while (right - left > 1){const auto mid = left + (right - left) / 2;if (GetLessEqualSumNum(pre, cur, mid)>= m_iK){right = mid;}else{left = mid;}}vector<int> vRet;for (const auto& pr : pre){for (const auto& cu : cur){if (pr + cu <= right){vRet.emplace_back(pr + cu);}else{break;}}}sort(vRet.begin(), vRet.end());if (vRet.size() > m_iK){vRet.erase(vRet.begin() + m_iK, vRet.end());}return vRet;}int GetLessEqualSumNum(const vector<int>& pre, const vector<int>& cur,int iSum){int iNum = 0;for (const auto& pr : pre){iNum += std::upper_bound(cur.begin(), cur.end(), iSum - pr)- cur.begin();}return iNum;}int m_iK;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()
{
vector<vector> mat;
int k;
int res;
{
Solution slu;
mat = { {1,3,11},{2,4,6} };
k = 5;
res = slu.kthSmallest(mat, k);
Assert(7, res);
}
{
Solution slu;
mat = { {1,3,11},{2,4,6} };
k = 9;
res = slu.kthSmallest(mat, k);
Assert(17, res);
}
{
Solution slu;
mat = { {1,10,10},{1,4,5},{2,3,6} };
k = 7;
res = slu.kthSmallest(mat, k);
Assert(9, res);
}
{
Solution slu;
mat = { {1,1,10},{2,2,9} };
k = 7;
res = slu.kthSmallest(mat, k);
Assert(12, res);
}
//CConsole::Out(res);
}
優化增加結果
vector<int> vRet;for (const auto& pr : pre){for (const auto& cu : cur){if (pr + cu < right){vRet.emplace_back(pr + cu);}else{break;}}}while (vRet.size() < m_iK){vRet.emplace_back(right);}
和小于right的數量<=k，如果不足夠，則補right。時間復雜度由O(nk)降低到O(k+n)。
直接使用封裝類
namespace NBinarySearch
{template<class INDEX_TYPE,class _Pr>INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE right, _Pr pr){while (right - left > 1){const auto mid = left + (right - left) / 2;if (pr(mid)){right = mid;}else{left = mid;}}return right;}
}class Solution {
public:int kthSmallest(vector<vector<int>>& mat, int k) {m_c = mat.front().size();m_iK = k;vector<int> pre = mat[0];for (int r = 1; r < mat.size(); r++){pre = GetLessKSum(pre, mat[r]);}return pre.back();}vector<int> GetLessKSum(const vector<int>& pre, const vector<int>& cur){auto GetLessEqualSumNum = [&pre, &cur, this](const int iSum)-> bool{int iNum = 0;for (const auto& pr : pre){iNum += std::upper_bound(cur.begin(), cur.end(), iSum - pr) - cur.begin();}return iNum >= m_iK;};const int right = NBinarySearch::FindFrist(0, 5000 * 40, GetLessEqualSumNum); vector<int> vRet;for (const auto& pr : pre){for (const auto& cu : cur){if (pr + cu < right){vRet.emplace_back(pr + cu);}else{break;}}}while (vRet.size() < m_iK){vRet.emplace_back(right);}sort(vRet.begin(), vRet.end());if (vRet.size() > m_iK){vRet.erase(vRet.begin() + m_iK, vRet.end());}return vRet;}int GetLessEqualSumNum(const vector<int>& pre, const vector<int>& cur,int iSum){int iNum = 0;for (const auto& pr : pre){iNum += std::upper_bound(cur.begin(), cur.end(), iSum - pr)- cur.begin();}return iNum;}int m_iK;int m_c;
};
2023年3月暴力版
直接保留前k個。時間復雜度:O(mknlogk)
class Solution {
public:
int kthSmallest(vector<vector>& mat, int k) {
m_r = mat.size();
m_c = mat[0].size();
std::priority_queue pre;
pre.push(0);
for (int r = 0; r < mat.size(); r++)
{
std::priority_queue dp;
while (pre.size())
{
int t = pre.top();
pre.pop();
for (int c = 0; c < m_c; c++)
{
dp.push(mat[r][c] + t);
if (dp.size() > k)
{
dp.pop();
}
}
}
pre.swap(dp);
}
return pre.top();
}
int m_r, 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 C++17
或者 操作系統：win10 開發環境：
VS2022 C++17
本文涉及的基礎知識點
C++算法：前綴和、前綴乘積、前綴異或的原理、源碼及測試用例 包括課程視頻
