Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 378. Kth Smallest Element in a Sorted Matrix

---

參考資訊：
https://www.cnblogs.com/grandyang/p/5727892.html

題目：


解答：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int l = matrix[0][0];
        int r = matrix.back().back();

        auto less_cnt = [&](int m) {
            int i = matrix.size() - 1;
            int j = 0;
            int n = matrix[0].size();
            int cnt = 0;

            while (i >= 0 && j < n) {
                if (matrix[i][j] <= m) {
                    cnt += i + 1;
                    j += 1;
                }
                else {
                    i -= 1;
                }
            }

            return cnt;
        };
        
        while (l < r) {
            int m = l + ((r - l) >> 1);

            int c = less_cnt(m);
            if (c < k) {
                l = m + 1;
            }
            else {
                r = m;
            }
        }

        return l;
    }
};