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

链接：1439.有序矩阵中的第k个最小数组和
难度：Hard
标签：数组、二分查找、矩阵、堆（优先队列）
简介：给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。

题解 1 - cpp

• 编辑时间：2023-05-28
• 执行用时：156ms
• 内存消耗：32.9MB
• 编程语言：cpp
• 解法介绍：每次求和只取前k个数字，后面数字不需要。

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        vector<int> list(1, 0);
        for (auto &m : mat) {
            vector<int> next;
            for (auto &num1 : list) {
                for (auto &num2 : m) {
                    next.push_back(num1 + num2);
                }
            }
            sort(next.begin(), next.end());
            if (next.size() > k) next.resize(k);
            list = next;
        }
        return list.back();
    }
};

题解 2 - cpp

• 编辑时间：2023-05-28
• 执行用时：16ms
• 内存消耗：8.3MB
• 编程语言：cpp
• 解法介绍：求出最大最小值，二分答案。

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size(), l = 0, r = 0, base = 0;
        for (int i = 0; i < n; i++) l += mat[i][0], r += mat[i][m - 1], base += mat[i][0];
        function<bool(int, int, int&)> dfs = [&](int idx, int sum, int &cnt) {
            if (idx == -1) return --cnt == 0;
            for (int i = 0; i < mat[idx].size() && sum - (mat[idx][i] - mat[idx][0]) >= 0; i++)
                if (dfs(idx - 1, sum - (mat[idx][i] - mat[idx][0]), cnt)) return true;
            return false;
        };
        while (l < r) {
            int m = (l + r) / 2, cnt = k;
            if (dfs(n - 1, m - base, cnt)) r = m;
            else l = m + 1;
        }
        return l;
    }
};