这是力扣网站的一道题，题目给了一个例子 matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8 我们把它拆分成这样几个矩阵
[1][ [ 1, 5] [10, 11] ][ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]我们会发现每个矩阵最后一个元素会是这个矩阵里值最大的元素，我们要找第8小的元素，第一个矩阵只有1个元素，第二个矩阵有4个元素，所以不在这两个矩阵里，第三个矩阵有9个元素，所以我们要找的肯定是图中标亮的几个元素的一个
规律找到了以后，接下来要解决的就是怎么查找了 如果我们用暴力查找的话，也可以做出来，但是时间复杂度会比较大，所以我们思考还有没有别的更加快的查找方式 我们知道，二分查找是效率比较高的查找方式，但它需要数组有序，我们观察题目，会发现其实这个二维数组其实是相对有序的（其实我觉得题目给的例子还是比较特殊的，这个等会再说） 这里用二分查找的思路是：找到这个二维数组的中间值，（不是中间索引号，这里跟一维数组的情况不太一样），然后求出这个中间值是第几小的元素，如果比k大，那么说明k指向的数在它的“前边”，否则在它的“后边”
var kthSmallest = function(matrix, k) { let n = matrix.length; if(k > n * matrix[0].length || !matrix) return 0; let low_v = matrix[0][0]; let high_v = matrix[n-1][n-1]; //用二分查找的原理 while(low_v <= high_v){ let mid_v = Math.floor((low_v + high_v) / 2); let rank = getRank(matrix, mid_v); //rank记mid_v是第几大的元素 if(rank < k){ low_v = mid_v + 1; } else{ high_v = mid_v - 1; } } return low_v; }; function getRank(matrix, value){ let n = matrix.length; let rank = 0; let i = 0, j = n - 1; //i为行，j为列 while(i < n && j >= 0){ if(value >= matrix[i][j]){ //比当前行的最大值还要大，就比较下一行 rank += j + 1; i++; } else{ //比当前行最大值小，留在当前行继续比较 j--; } } return rank; };matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8
应用前面找出的规律，最小值为1，最大值为15，中间值为8求8的级别，先看第0行最后一个元素9，8<9说明8应该在第0行和第0行倒数第2个元素5比，8>5，计算rank为2再看下一行，现在是8和matrix[1][1]比，8<11，和matrix[1][0]比，8<10，j–后小于0了，查找结束，返回rank，所以k指向的数在后半部分下一次查找，最小值为9，最大值为15，中间值为12，同样的方法，比较顺序为9->13->11->13->12，返回rank为6下一次查找，最小值为13，最大值为15，中间值为14，比较顺序为9->13->15->13,返回rank值为8，rank不小于k结束，要求的就是最小值13matrix = [ [ 1, 3, 5], [2, 4, 9], [7, 8, 10] ], k = 8 1.low_v=1,high_v=10,mid_v=5 matrix = [ [ 1, 3, 5], [2, 4, 9], [7, 8, 10] ] rank = 3 + 2 < 8 2.low_v=6,high_v=10,mid_v=8 matrix = [ [ 1, 3, 5], [2, 4, 9], [7, 8, 10] ] rank = 3 + 2 + 2 < 8 3.low_v=9,high_v=10,mid_v=9 matrix = [ [ 1, 3, 5], [2, 4, 9], [7, 8, 10] ] rank = 3 + 3 + 2 = 8, 即要求的是9
