LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 每行每列均为升序，第一行第一个元素即为最小元素，最后一行最后一列即为最大元素，在最小元素到最大元素中二分查找即可

class Solution {
 public:
  int kthSmallest(vector<vector<int>>& matrix, int k) {
    int l = matrix[0][0];
    int r = matrix.back().back();
    while (l < r) {
      int m = l + (r - l) / 2;
      int cnt = 0;  // 记录不大于m的元素数
      for (auto& x : matrix) {
        cnt += upper_bound(begin(x), end(x), m) - begin(x);
      }
      if (k <= cnt) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    return l;
  }
};