378. Kth Smallest Element in a Sorted Matrix

bisection O(nlognlogD) time where D是最大最小值之差
用这个二分猜数

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            int cnt = 0;
            for (const auto &v : matrix) { // 统计所有不大于m的数的个数
                cnt += (upper_bound(v.begin(), v.end(), m) - v.begin());
            }
            if (cnt < k) { // 如果不大于m（包括m）的数不到k个，说明m不是最终结果
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        return lo;
    }
};

O((n+n²-k)logn)

struct cmp {
    bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs) {
        return lhs.first < rhs.first;
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        const int target = matrix.size() * matrix.size() - k;
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
        for (int row = 0; row < matrix.size(); ++row) {
            heap.push(make_pair(matrix[row].back(), row));
            matrix[row].pop_back();
        }
        for (int i = 0; i < target; ++i) {
            auto p = heap.top();
            heap.pop();
            if (!matrix[p.second].empty()) {
                heap.push(make_pair(matrix[p.second].back(), p.second));
                matrix[p.second].pop_back();
            }
        }
        return heap.top().first;
    }
};

O(n³)

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int size = matrix.size() * matrix.size() - k + 1;
        for (int i = 0; i < size; ++i) {
            int max_num = INT_MIN;
            int max_row = matrix.size() - 1;
            for (int row = matrix.size() - 1; row >= 0; --row) {
                if (!matrix[row].empty() && matrix[row].back() > max_num) {
                    max_num = matrix[row].back();
                    max_row = row;
                }
            }
            if (i == size - 1)
                return matrix[max_row].back();
            matrix[max_row].pop_back();
        }
        return 0;
    }
};