378. Kth Smallest Element in a Sorted Matrix

Leetcode

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

題目

Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

解答

• 方法一

矩陣的列會往右遞增、欄會往下遞增，故左上角一定是最小的數字，右下角一定是最大的數字。根據以上條件，我們可以把最小值設成左上的值、最大值為右下的值，進行 binary search，最初拿 mid 值去跟矩陣左下角的數字比較，逐步求得矩陣有多少個數(cnt)其數值是小於 mid 的 (如果 mid > 左下角值代表 mid 也大於這整欄所有的數值，所以 cnt += row 的列數，再依序往右、往上尋找，最終找出多少個數字是小於 mid 的)，如果 cnt 小於 k，代表我們的 mid 值太小，所以要往數值大的方向尋找 (mid+1 ~ end)，最終當 start 與 end 值相同的時候，就是我們要找的數字了。

var kthSmallest = function(matrix, k) {
  const n = matrix.length;

  function getCntLowerThen(value) {
    let cnt = 0;
    let row = n - 1;
    let col = 0;

    while (row >= 0 && col < n) {
      if (matrix[row][col] <= value) {
        cnt += row + 1;
        col++;
      } else {
        row--;
      }
    }
    return cnt;
  }

  let start = matrix[0][0];
  let end = matrix[n - 1][n - 1];
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    const cnt = getCntLowerThen(mid);

    if (cnt < k) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }

  return start;
}

Runtime: 60 ms, faster than 99.65% of JavaScript online submissions for Kth Smallest Element in a Sorted Matrix. O(n*lg(max-min))

Memory Usage: 41.3 MB, less than 98.96% of JavaScript online submissions for Kth Smallest Element in a Sorted Matrix.

https://anj910.medium.com/leetcode-378-kth-smallest-element-in-a-sorted-matrix-%E4%B8%AD%E6%96%87-318d52f366af

測資

let matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8;

console.log(kthSmallest(matrix, k));

參考資料

1. https://anj910.medium.com/leetcode-378-kth-smallest-element-in-a-sorted-matrix-%E4%B8%AD%E6%96%87-318d52f366af