在一个排序矩阵中找从小到大的第 k 个整数。 排序矩阵的定义为：每一行递增，每一列也递增。

在线评测地址

样例 1:

输入: [   [1 ,5 ,7],   [3 ,7 ,8],   [4 ,8 ,9], ] k = 4 输出: 5 

样例 2:

输入:  [   [1, 2],   [3, 4] ] k = 3 输出: 3 

算法：二分

题目中矩阵 n 行 m 列，每行每列都是单调的，我们可以按照行或者列做 把 n 行当成 n 个数组 即求 n 个有序数组里第 k 小值是多少

如果序列有序，则可以用一种更有效率的查找方法来查找序列中的记录，这就是折半查找法，又称为二分搜索。 折半查找的基本思想：减少一半的查找序列的长度，分而治之地进行关键字的查找。他的查找过程是：先确定待查找记录的所在的范围，然后逐渐缩小查找的范围，直至找到该记录为止（也可能查找失败）。 在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

本题思路

1. 二分第 k 小的是多少 二分解决判定性问题 我们二分出来第 k 小是 x， 统计出有 num 个元素小于等于 x 如果 num≥k 我们就可以减小上界 否则就可以提高下界
2. 对于二分出来的 x，判断有多少个元素是小于等于 x 的 我们可以先找元素大于 x 的，然后再用元素总个数减去大于 x 的元素个数 如何求有多少大于 x 的元素，我们可以再用一次二分查找 upperbound 函数，对 n 个数组都执行一次 upperbound 查找每个数组有多少比 x 大的

import java.util.Comparator;import java.util.PriorityQueue; public class Solution {      public long calc(int x, int[][] matrix) {         long num = 0;         for(int i = 0; i < matrix.length; i++) {             int left = -1, right = matrix[i].length, pos = -1;             //二分 upper_bound 查找多少个比 x 大的             while(left + 1 < right) {                 int mid = left + (right - left) / 2;                 if(matrix[i][mid] > x) {                     right = mid;                     pos = mid;                 } else {                     left = mid;                 }             }             if(pos == -1) {                 num += 0;             } else {                 num += matrix[i].length - pos;             }         }         return num;     }     /**      * @param matrix: a matrix of integers      * @param k: An integer      * @return: the kth smallest number in the matrix      */     public int kthSmallest(int[][] matrix, int k) {         // write your code here         int left = matrix[0][0], right = matrix[0][0];          //矩阵行数         long n = matrix.length;         //矩阵列数         long m = matrix[0].length;         for(int i = 0; i < n; i++) {             for(int j = 0; j < m; j++) {                 //确定二分上下界                 left = Math.min(left, matrix[i][j]);                 right = Math.max(right, matrix[i][j]);             }         }         left -= 1;         right += 1;         while(left + 1 < right) {             //判定 mid 是不是第 k 小             int mid = left + (right - left) / 2;             long num = calc(mid, matrix);             //如果比 mid 小的超过 k 个，就可以缩小上界，否则提高下界             if(n * m - num >= (long)k) {                 right = mid;             } else {                 left = mid;             }         }         return right;     } } 

大佬有話說 (0)