本文涉及的基础知识点
本题的简化
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);
