leetcode 378题 有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
思路
1 排序实现
2 优先队列 未达到k时，一直push，到达k时，判断队列头是否大于当前值，若是，需要替换队列头为当前值
代码
function flat(arr) {
return arr.reduce((prev, cur) => {
if (Array.isArray(cur)) {
return [...prev, ...flat(cur)]
}
prev.push(cur);
return prev;
}, []);
}
function kthSmallest(matrix, k) {
const arr = flat(matrix).sort((a, b) => a-b);
return arr[k-1];
}
class priorityQueue {
constructor() {
this.data = [];
}
push(val) {
for (let i=0; i<this.data.length; i++) {
if (this.data[i] <= val) {
this.data.splice(i, 0, val);
return;
}
}
this.data.push(val);
}
poll() {
if (this.data.length) {
return this.data.shift();
}
}
peek() {
return this.data[0];
}
size() {
return this.data.length;
}
}
function kthSmallest(matrix, k) {
const pq = new priorityQueue();
for (let i=0; i<matrix.length; i++) {
for (let j=0; j<matrix[i].length; j++) {
if (k === pq.size()) {
if (pq.peek() > matrix[i][j]) {
pq.poll();
pq.push(matrix[i][j]);
}
} else {
pq.push(matrix[i][j]);
}
}
}
return pq.data[0];
}
复杂度分析
- 时间复杂度: O(N^2)
- 空间复杂度: O(1)