优化增加结果
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
