LC_有序矩阵中第K小的元素

仰望星空 2023/11/29 LeetCode堆排序

https://leetcode-cn.com/leetbook/read/top-interview-questions/xaicbc/

这道题可以用最小堆和排序来做，但最小堆在JavaScript中没有 API，笔者只是用了排序来做：

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
  let arr = matrix.reduce((a,b)=>{
    return a.concat(b);
  })

  arr.sort((a, b) => {
    return a - b;
  })

  return arr[k-1];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结果是击败了 60% 的 JavaScript 用户，然后根据题目中的有序信息，改写了代码，先排除掉右下角那些必定大于第 k 大的元素，然后再对剩下的排序。

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (matrix, k) {
  let m = Math.sqrt(k * 2);
  m = Math.ceil(m) + 1;

  let arr = [];
  for (let row of matrix) {
    let rr = row.slice(0, m);
    arr.push(...rr);
  }

  arr.sort((a, b) => {
    return a - b;
  })

  return arr[k - 1];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

然而，实际运行结果和第一种差不多，可能是因为第二种只是缩小了规模，并没有降低时间复杂度。