这道题虽然标的是Medium，但是我觉得绝对是Hard难度，代码虽然不长，但是代码后面的逻辑思考还是难度不少的，第一次碰到同类型的很难做出来

难点1: Binary Search可以不基于Index，而基于Number Range

  • 给定一个数（中点），看看比它小的数是不是k个
    • 如果小于k，则我们想要找的数必然比这个数大
    • 如果大于等于k，则我们找的数则必然小于等于这个数

代码如下：

  1. class Solution {
  2.   public int kthSmallest(int[][] matrix, int k) {
  3.     int n = matrix.length;
  4.     int lo = matrix[0][0];
  5.     int hi = matrix[n-1][n-1];
  6.     while (lo < hi) {
  7.       int mi = lo + (hi - lo) / 2;
  9.       int j = n - 1;
  10.       int count = 0;
  11.       for (int i = 0; i < matrix.length; ++i) {
  12.         while (j >= 0 && matrix[i][j] > mi) {
  13.           --j;
  14.         }
  15.         count += (j + 1);
  16.       }
  17.       if (count < k) {
  18.         lo = mi + 1;
  19.       }
  20.       else {
  21.         hi = mi;
  22.       }
  23.     }
  25.     return lo;
  26.   }
  27. }
  • 空间复杂度：378. Kth Smallest Element in a Sorted Matrix - 图1
  • 时间复杂度：378. Kth Smallest Element in a Sorted Matrix - 图2
    • 这个是range based的Binary Search
    • 最大值是max,最小值是min

难点2:lo必然是matrix里面的数，且就是我们要找的答案

  • 存在数lo-1: 小于等于这个数的必然比k小
  • lo：小于等于这个数的大于等于k，两种可能
    • matrix里有多个lo，此时大于k
    • matrix里有一个lo，此时等于k
    • 不存在其他可能