378. 有序矩阵中第 K 小的元素 #

原题链接：LeetCode 378. 有序矩阵中第 K 小的元素

题目描述 #

给你一个 n x n* *矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

示例 1：

**输入：**matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 **输出：**13 **解释：**矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

**输入：**matrix = [[-5]], k = 1 输出：-5

提示：

- `n == matrix.length`

- `n == matrix[i].length`

- `1 <= n <= 300`

-109 <= matrix[i][j] <= 109
- 题目数据 **保证** `matrix` 中的所有行和列都按 **非递减顺序** 排列

1 <= k <= n2

进阶：

- 你能否用一个恒定的内存(即 `O(1)` 内存复杂度)来解决这个问题?

你能在 `O(n)` 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

难度： Medium

题解代码 #

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
// 内置堆
var kthSmallest = function(matrix, k) {
  const pq = new MinPriorityQueue({ 
    compare: (a, b) => matrix[a[0]][a[1]]  - matrix[b[0]][b[1]] 
  });
  const len = matrix[0].length
  const len1 = Math.min(matrix.length, k)

  for (let i = 0; i < len1; i++) {
    pq.enqueue([i, 0])
  }

  while (k-- >= 0 && pq.size()) {
    const [i, j] = pq.dequeue();
    if (!k) return matrix[i][j]
    if (j + 1 < len) pq.enqueue([i, j + 1]);
  }
};