LeetCode算法网站算法题
https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
1.最简单的直接排序
class Solution { vector<int>data; public: int kthSmallest(vector<vector<int>>& matrix, int k) { int row=matrix.size(); if(row==0) { return 0; } int col=matrix[0].size(); for(int i=0;i<row;i++) for(int j=0;j<col;j++) { data.push_back(matrix[i][j]); } sort(data.begin(),data.end()); return data[k-1]; } };2.归并排序——说实在的并不像归并排序
priority_queue<point, vector<point>, greater<point>>表示的是升序优先队列，较小的值放在队列前端，先把第一排的数据放入优先队列，再循环的每次弹出一个元素然后再判断是否可以再加入后一个元素（即当前队首元素并不是它这一行的最后一个数值），总共循环k-1次，之后优先队列的队首元素就是第k大的元素了。
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { struct point//存放数值大小和数值坐标 { int val, x, y; point(int val, int x, int y) : val(val), x(x), y(y) {} bool operator> (const point& a) const { return this->val > a.val; } }; priority_queue<point, vector<point>, greater<point>> que;//升序优先队列 int n = matrix.size(); for (int i = 0; i < n; i++) { que.emplace(matrix[i][0], i, 0);//把第一列的数值放进去 } for (int i = 0; i < k - 1; i++)//循环k-1次，每次弹出一个元素然后再判断是否可以再加入后一个元素，之后优先队列的队首元素就是第k大的元素了 { point now = que.top(); que.pop(); if (now.y != n - 1)//如果不是当前行的最后一个元素，就放入后一个更大的元素 { que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1); } } return que.top().val; } };3.二分查找——很独特的一种用法
check函数的算法
初始位置在 matrix[n−1]（即左下角）；
设当前位置为 matrix[i][j]。若 matrix[i][j]≤mid，则将当前所在列的不大于 mid的数的数量（即 i+1）累加到答案中，并向右移动，否则向上移动；
不断移动直到走出格子为止。
所以最终small 的值是小于等于mid 的值的个数。
接着，不妨假设答案为 x，那么可以知道 l≤x≤r，这样就确定了二分答案的上下界。
每次对于「猜测」的答案 mid，计算矩阵中有多少数不大于 mid ：
如果数量不多于 k，那么说明最终答案 x不小于 mid； 如果数量少于 k，那么说明最终答案 x 大于 mid。
这样我们就可以计算出最终的结果 x了。
class Solution { private: bool check(vector<vector<int>>&num,int mid,int k,int n) { int small=0; int i=n-1; int j=0; while(i>=0&&j<n) { if(num[i][j]<=mid) { small+=i+1;//当前所在列不大于mid的数量 j++; } else { i--; } } return small>=k; } public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); int left=matrix[0][0]; int right=matrix[n-1][n-1]; while(left<right) { int mid=left+(right-left)/2; if(check(matrix,mid,k,n)) right=mid; else left=mid+1; } return left; } };然后我改了一下就直接再次提交，就发现了我自己的一个毛病！！
class Solution { private: bool check(vector<vector<int>>&num,int mid,int k,int n) { int small=0; int i=n-1; int j=0; while(i>=0&&j<n) { if(num[i][j]<=mid) { small+=i+1;//当前所在列不大于mid的数量 j++; } else { i--; } } return small<=k; } public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); int left=matrix[0][0]; int right=matrix[n-1][n-1]; while(left<right) { int mid=left+(right-left)/2; if(check(matrix,mid,k,n)) left=mid; else right=mid-1; } return left; } };这样改写代码的话，问题就凸显出来了，我得到评论区的一位兄弟的解答： 1.假如还剩下最后两个数，由于取中值的操作是偏左处理的所以mid是指向left的，如果此时的check函数任然判断为真，那么left从新指向自己，就会形成死循环了； 2.把返回的条件改成small<=k的话，可能最终得到的值并不是矩阵内的，举个例子：矩阵是[[1, 2], [2, 5]]，k是3，那么答案应该是2，但是得到的却是4，虽然小于4的数确实有3个，但是4不是矩阵中的数字，small<=k得到的是最后一个满足条件的数字，因为只要满足samll<=k我就移动左指针从而得到最后一个值，但是这个题应该找的是第一个满足条件的数字，因为第一个满足条件的数字才会在矩阵中，所以应该用small>=k
