给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例：
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,
返回 13。
提示： 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
——题目难度:中等
关于优先队列的使用 可以看看这篇——215. 数组中的第K个最大元素(C++)---基于快排的方法 / 基于堆排序的方法(包含优先队列的使用总结) 思路大概是：可以限制一个元素大小为k的大顶堆，当遍历完一遍matrix后，队首元素就是第 k 小的元素了（依赖于优先队列内部的自动排序）。-使用优先队列解题代码如下(精简版)
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { priority_queue<int, vector<int>, less<int>> pq; for(int i = 0; i < matrix.size(); i++) { for(int j = 0; j < matrix[0].size(); j++) { pq.push(matrix[i][j]); if (pq.size() > k) pq.pop(); } } return pq.top(); } };上面的代码运行起来有点慢，是因为pq.push(matrix[i][j]); 。 因为不加判断 直接加入队列，这样优先队列内部进行的自动排序 次数就会变多，所以运行起来也就越慢。-下面的改进的代码(增加判断语句 以 减少队列内部进行的自动排序的次数)
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { priority_queue<int, vector<int>, less<int>> pq; for(int i = 0; i < matrix.size(); i++) { for(int j = 0; j < matrix[0].size(); j++) { int temp = matrix[i][j]; if (pq.size() == k && temp < pq.top()) { pq.pop(); pq.push(temp); } else if (pq.size() == k) { continue; } else { pq.push(temp); } } } return pq.top(); } };←这样比之前快了一点点。
解法参考力扣—官方题解里的二分解法，在进行模拟二分法的时候 可以把 二维数组matrix里的 全部元素 看成 排好序的 一维数组，这样可以比较好理解此题的二分解法。 且不用担心 这里的二分法 找不到那个待求数，因为每次循环中都保证了第k小的数在left~right之间，当left==right时，第k小的数即被找出，等于left(right也是一样的)。可以通过直接想象，二分法不断排除掉不符合条件的元素，一定保留了是正确答案的元素，缩小了搜索区间。 举个例子，当 matrix = [ [ 1, 3, 5], [7, 9, 11], [13, 15, 17] ], k = 3， 直观可以看出第3小元素，即答案为 5 二分法后，退出循环之前的最后一步，搜索区间如果为 [4, 5]（因为搜索区间一定保留了是正确答案的元素），因为还能缩小区间 但是你不可能把正确答案 5 丢弃吧？并且 mid = 4 不满足题意，直接舍弃，将 left = 5。那区间只剩下 5 了， 5 即为正确答案。 二分法后，退出循环之前的最后一步，搜索区间如果为 [5, 6]（因为搜索区间一定保留了是正确答案的元素），同样，因为还能缩小区间 但是你不可能把正确答案 5 丢弃吧？ mid = 5，那既然还满足条件，那我就看看能不能再缩小下区间，那么就只能将 right = 5了，那区间只剩下 5 了， 5 即为正确答案。
具体证明如下： 设 left{t} 表示第 t 轮二分的 left，mid{t} 为第 t 轮二分的 mid，right{t} 为第 t 轮二分的 right，target 是目标值(首先此题中 target 肯定是矩阵中的某个值，因为由于某种判断，判断出 mid > target 的话，会因为满足循环条件而缩小 right，由于某种判断，判断出 mid < target 的话，也同样会增大 left。这里的某种判断会根据matrix数组里的元素做判断，这样就会导致 target 就是 matrix 数组里的元素)。
left{t} = left{t-1} 或者 mid{t-1} + 1。 ①如果 left{t}=mid{t-1} + 1,说明小于等于 mid{t-1} 的矩阵中元素的个数小于 k, 说明 mid{t-1} < target,那么 left{t} = mid{t-1} + 1< target + 1, 也就 left{t} - 1 < target，即 left{t} <= target(因为 left{t} 和 target 都是整数)。 因此，只要其中有一次的 left 是由上一轮的 mid 转化而来的，那么就可以保证 left 始终<= target。 ②如果min一直保持着初始状态，从来没有从上一轮 mid 转化而来过，那么 left{t} = left{1} <= target ( left{1} <= target 是肯定的，因为一开始 target 只能是 left{1} 或是在 left{1} 的右边)。因此，left 始终小于等于 target。
差不多的，right{t} = mid{t-1} 或者 right{t-1}。 ①如果 right{t} = mid{t-1},说明小于等于 mid{t-1} 的矩阵中的元素的个数 >= k，说明 mid{t-1} >= target。因此，只要其中有一次的 right 是由上一轮的 mid 转化而来的，那么就可以保证 right 始终 >= target。 ②如果 right 一直保持着初始状态，从来没有从上一轮 mid 转化而来过，那么 right{t} = right{1} >= target ( right{1} >= target 是肯定的，因为一开始 target 只能是 right{1} 或是在 right{1} 的左边)。因此，right 始终大于等于 target。 综上所述，由于 left 和 right 构成的区间是在不断缩小的，所以最终肯定可以达到 left = right 的状态，从而退出循环。 此时，因为 left <= target，right >= target，又 left = right， 那么 肯定有 left = right = target ！！
——参考一位大神的推导。
-解题代码
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 mid = (l + r) / 2; int count = search_less_count(matrix, mid); if (count < k) { l = mid + 1; } else { r = mid; } } return l; } int search_less_count(vector<vector<int>>& matrix, int target) { int cnt = 0; //从左下角开始查找 int n = matrix.size(); int i = n - 1, j = 0; while (i >= 0 && j < n) { if (target >= matrix[i][j]) { cnt += i + 1; j++; } else { i--; } } return cnt; } };