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

有序矩阵中第 K 小的元素

题目

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

思路（值域二分 + 计数）

矩阵非空且为整数矩阵，每行每列非递减，允许重复。第 k 小按重复元素分别计数，不是第 k 个不同值。原题为 n × n，代码中的计数也适用于规则的 m × n 矩阵，要求 1 ≤ k ≤ mn。

二分寻找最小的整数 x，使 count(<= x) >= k。这是值域二分，不是直接二分矩阵的展平下标。

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

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

每次计数最多向上 m 步、向右 n 步，为 O(m+n)。令 R = max - min + 1，总时间 O((m+n) log R)，额外空间 O(1)；JavaScript Number 运算依赖题目给定整数范围，不适用于任意大整数矩阵。

代码（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;
};