给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于 O(n2) 的解决方案。
示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：
输入：matrix = [[-5]], k = 1
输出：-5
提示：
- n == matrix.length
- n == matrix[i].length
- 1
class Solution {
public int kthSmallest(int[][] matrix, int k) {
// 矩阵行数
int n = matrix.length;
// 矩阵列数
int m = matrix[0].length;
// 有序矩阵的最小值，即矩阵左上角的值
int left = matrix[0][0];
// 有序矩阵的最大值，即矩阵右下角的值
int right = matrix[n - 1][m - 1];
// 矩阵中第k小的数
int ans = 0;
// 记录小于等于mid这个数的信息，包含小于等于mid的数有多少个和小于等于mid并且最接近mid的数是什么
Info equalOrLessMidInfo = null;
// 利用二分法，找到小于等于mid的数正好有k个的信息
while (left > 1);
// 获取矩阵中小于等于mid的Info信息，包括小于等于mid的个数，和小于等于mid的数中最接近mid的数是什么
equalOrLessMidInfo = getequalOrLessNumInfo(matrix, mid);
// 如果小于等于mid的数少于k个，意味着我们还需要提高mid的值
if (equalOrLessMidInfo.equalOrLessNumCnt < k) {
// 取右半部分
left = mid + 1;
// 这个分支需要注意:
// 如果小于等于mid的数大于k个，意味着我们还需要减少mid的值，尝试找到正好等于k个的值
// 但是一定存在一个mid，正好使得矩阵中小于等于它的数有k个吗？并不一定，因为矩阵中可能存在重复的数。
// 假设要找第7小的数，矩阵中从小到大排列出来是1、2、3、4、5、5、5、5、6、7
// 正确答案应该是5，5是这个矩阵中第7小的数，但是在这个代码中是无法找到一个mid使小于等于它的数有7个的
// 比如如果找小于等于5，最后的结果就是8个，如果找小于等于6，结果就是9个，小于等于4，结果就是4个
// 所以并不能保证一定能找到equalOrLessMidInfo.equalOrLessNumCnt == k的结果，有可能equalOrLessMidInfo.equalOrLessNumCnt > k，但是最终的结果就在这个equalOrLessMidInfo中。
// 所以，我们需要在等于k和大于k的时候都去记录一下ans，因为这个时候的equalOrLessMidInfo.nearNum都有可能是答案
// 不用记录equalOrLessMidInfo.equalOrLessNumCnt < k的情况，因为如果此时小于等于mid的数都不够k个，就不可能找到矩阵中第k小的数，答案一定不在这种情况中。
} else if (equalOrLessMidInfo.equalOrLessNumCnt >= k) {
// 如果存在小于等于Mid的数正好有k个，那么此时的距离mid最近的数一定就是答案了，就算是继续执行这个while循环，也永远不会进入到这个分支了，因为这里会取左半部分，会降低下一轮mid的值，那么必然就会使小于mid的值变得小于k
// 如果如果存在小于等于Mid的数正好大于k个，就会继续执行循环，找更小的mid来尝试能不能找到更接近k个的解。但是同时也会将此时的最接近mid的值作为临时的答案，如果后面的循环再也进不到这个分支了，那是因为后面的都不足k个了，答案不可能在不足k个的情况里，所以这一次记录的临时答案就是最终的答案，这个答案在矩阵中肯定是存在相同的值的
ans = equalOrLessMidInfo.nearNum;
// 取左半部分
right = mid - 1;
}
}
return ans;
}
public class Info {
// 小于等于num并且最接近num的数是多少
int nearNum;
// 小于等于num的数一共有多少个
int equalOrLessNumCnt;
public Info(int nearNum, int equalOrLessNumCnt) {
this.nearNum = nearNum;
this.equalOrLessNumCnt = equalOrLessNumCnt;
}
}
// 找到矩阵中小于等于num的数有多少个，并且小于等于num且最接近它的数是多少
public Info getequalOrLessNumInfo(int[][] matrix, int num) {
// 从右上角开始
int row = 0;
int col = matrix[0].length - 1;
// 记录小于等于num的个数
int cnt = 0;
// 记录小于等于num并且最接近num的数是多少
int ans = Integer.MIN_VALUE;
while (row = 0) {
// if (matrix[row][col] == num) {
// ans = matrix[row][col];
// cnt += (col + 1);
// return new Info(ans, cnt);
// }
// 如果matrix[row][col] == num，有可能这个位置就是答案点，也有可能它的下一行还会有符合要求的，所以记录一下临时答案，然后再去下一行看有没有小于等于num的数，如果有的话，就再加上这一部分才不会遗漏答案。因为这个矩阵只是列和行有序的，但是不同行不同列并不存在严格的有序性，所以还需要额外判断判断一下
if (matrix[row][col] num) {
// 就向左移动一个位置，去看左边的位置能不能小于等于num，因为左边都是比自己小的数
col--;
}
}
// 返回答案
return new Info(ans, cnt);
}
}
整个流程就是求两个信息：
1、小于等于某一个值的个数有几个。
2、当找到小于等于某一个值的数的数量等于我们的目标数量时，就去求最接近它的是谁？
Original: https://blog.csdn.net/cy973071263/article/details/127812277
Author: 小七mod
Title: 【LeetCode】有序矩阵中第 K 小的元素 [M]（二分）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/655530/
转载文章受原作者版权保护。转载请注明原作者出处！