交完这题的感受是,这也能过?难怪这场周赛血崩啊啊啊……

4. 有序矩阵中的第 k 个最小数组和

给你一个 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 <= mati <= 5000
  • mat[i] 是一个非递减数组

思路

看到数据范围,尤其是 k 最大只能是 200 的时候,直接暴力就可以了。
有一点点DP的思想,求完前 i 行的最少 k 个数组和之后,再将这些和与第 i + 1 行的前 k 个数字求和,求得的 k^2 个和,取最小的 k 个供下一行使用。用优先队列维护即可。

代码

写的好丑的喔!!

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        priority_queue<int, vector<int>, greater<int>> que;
        for(int i=0; i<n; i++) que.push(mat[0][i]);
        for(int i=1; i<m; i++) {
            vector<int> pre;
            int cnt = 0;
            for(int j=0; j<k; j++) {
                if(que.empty()) break;
                pre.push_back(que.top());
                que.pop();
                cnt++;
            }
            while(!que.empty()) que.pop();
            for(int j=0; j<n; j++) {
                for(int kk=0; kk<cnt; kk++) {
                    que.push(pre[kk] + mat[i][j]);
                }
            }
        }
        int ans = 0;
        for(int i=0; i<k; i++) {
            ans = que.top();
            que.pop();
        }
        return ans;
    }
};
最后修改:2020 年 05 月 05 日 11 : 07 AM
如果觉得我的文章对你有用,请随意赞赏