[!info] related notes 算法面试题型 MOC 二分查找

有序矩阵中第 K 小的元素

题目

378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode）

思路（值域二分 + 计数）

矩阵每行每列递增。二分答案 x，并计算矩阵里 <= x 的元素个数。

计数技巧：从左下角 (i=m-1, j=0) 出发：

• 若 matrix[i][j] <= x，这一列从 0..i 都 <= x，计数加 i+1，然后 j++
• 否则 i--

复杂度：O(m+n) 计数一次，总体 O((m+n) log(range))。

代码（JavaScript）

function countLE(matrix, x) {
  const m = matrix.length;
  const n = matrix[0].length;
  let i = m - 1;
  let j = 0;
  let cnt = 0;
  while (i >= 0 && j < n) {
    if (matrix[i][j] <= x) {
      cnt += i + 1;
      j++;
    } else {
      i--;
    }
  }
  return cnt;
}

var kthSmallest = function(matrix, k) {
  let lo = matrix[0][0];
  let hi = matrix[matrix.length - 1][matrix[0].length - 1];
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (countLE(matrix, mid) >= k) hi = mid;
    else lo = mid + 1;
  }
  return lo;
};