题目大意

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例:

matrix = [[ 1,  5,  9],[10, 11, 13],[12, 13, 15]
],
k = 8,返回 13。

解题思路

方法一：

考虑用堆结构，创建一个大小为N的小根堆，初始化时放入矩阵每一行的第1个元素。
然后从堆顶向外弹K次，第K次即所求结果。
注意：在将每个元素放入堆时，要记录该元素来自哪一行（该元素被弹出时能够找到该元行），该元素是这一行的第几个元素（该元素被弹出时能够找到该行的下一个元素，且能够判断是否到了最后）。

// 比较器
struct cmp
{bool operator()(const vector<int> &x, const vector<int> & y){return x[0] > y[0];}
};class Solution {
public:int kthSmallest(vector<vector<int>>& matrix, int k) {int n = matrix.size() - 1;int m = matrix[0].size() - 1;// 小根堆priority_queue<vector<int>, vector<vector<int>>, cmp>heap;for (int i = 0; i < n; i++){heap.push(vector<int>{matrix[i][0], i, 0});}int ans = 0;for (int i = 0; i < k; i++){vector<int>x = heap.top();heap.pop();ans = x[0];// 如果该元素不是当前行的最后一个元素，则将下一个元素放入堆中if (x[2] <= m){++x[2];x[0] = matrix[x[1]][x[2]];heap.push(x);}}return ans;}
};

方法二：

二分查找。这道题不同于常规的二分法（常见的二分法二分索引进行查找），本题直接二分元素进行查找。
首先在矩阵中，左上角的元素left最小，右下角的元素right最大。计算二者的均值mid（该元素不一定是矩阵中的元素！！！）。计算矩阵中小于等于mid的元素个数nums。

• 如果nums>=k，表示矩阵中小于等于mid的元素至少有K个，而我们要找矩阵中的第K个元素。所以应该缩小查找范围，即right=mid（right不能等于mid-1，因为mid可能是矩阵中的第K个元素）；
• 如果nums<k，表示矩阵中小于等于mid的元素不足K个（无论mid在不在矩阵中），矩阵中的第K个元素一定是大于mid的元素，因此扩大范围，即mid=left+1.

class Solution {
public:int kthSmallest(vector<vector<int>>& matrix, int k) {// 根据元素值二分查找int left = matrix[0][0];int right = matrix.back().back();while (left != right){int mid = left + (right - left) / 2;int count = 0, i = matrix.size() - 1, j = 0;// 计算矩阵中小于等于mid的元素个数while (i >= 0 && j < matrix.size()){if (mid < matrix[i][j])--i;else{count += (i + 1);++j;}}// 如果至少为K个，缩小范围if (count >= k)right = mid;// 不足k个，扩大范围else left = mid + 1;}return left;}
};