資訊專(zhuān)欄INFORMATION COLUMN
摘要：先放一行，或一列把堆頂?shù)淖钚≡厝〕鰜?lái)，取次，如果該有下一行下一列的，放入堆中最小的個(gè)元素已經(jīng)在上面的循環(huán)被完了，下一個(gè)堆頂元素就是
Problem
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n^2.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
Queue queue = new PriorityQueue((a, b)->a.val-b.val);
//先放一行，或一列
for (int i = 0; i < n; i++) queue.offer(new Node(i, 0, matrix[i][0]));
//把堆頂?shù)淖钚≡厝〕鰜?lái)，取k-1次，如果該node有下一行/下一列的node，放入堆中
for (int i = 0; i < k-1; i++) {
Node node = queue.poll();
if (node.y == n-1) continue;
else queue.offer(new Node(node.x, node.y+1, matrix[node.x][node.y+1]));
}
//最小的k-1個(gè)元素已經(jīng)在上面的for循環(huán)被poll完了，下一個(gè)堆頂元素就是kth smallest
return queue.poll().val;
}
}
class Node {
int x;
int y;
int val;
public Node(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72219.html
摘要：復(fù)雜度是，其中。這做法和異曲同工?？戳司W(wǎng)上給的解法，沒(méi)有二分，二分的是結(jié)果。每次找到一個(gè)，然后求比它小的元素的個(gè)數(shù)，根據(jù)個(gè)數(shù)大于還是小于來(lái)二分。參考算的時(shí)候可以?xún)?yōu)化 378. Kth Smallest Element in a Sorted Matrix 題目鏈接：https://leetcode.com/problems... 求矩陣?yán)锩娴趉小的數(shù)，首先比較容易想到的是用heap來(lái)做...
摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第個(gè)元素的值進(jìn)行堆排序就可以了。 題目要求 Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that...
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the...
摘要：中序遍歷復(fù)雜度時(shí)間空間思路因?yàn)樽蠊?jié)點(diǎn)小于根節(jié)點(diǎn)小于右節(jié)點(diǎn)，二叉搜索樹(shù)的一個(gè)特性就是中序遍歷的結(jié)果就是樹(shù)內(nèi)節(jié)點(diǎn)從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點(diǎn)時(shí)馬上退出。這樣我們就可以用二叉樹(shù)搜索的方法來(lái)解決這個(gè)問(wèn)題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...
摘要：解題思路本題需要找的是第小的節(jié)點(diǎn)值，而二叉搜索樹(shù)的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個(gè)情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...
閱讀 933·2023-04-26 01:34
閱讀 3367·2023-04-25 20:58
閱讀 3310·2021-11-08 13:22
閱讀 2121·2019-08-30 14:17
閱讀 2533·2019-08-29 15:27
閱讀 2683·2019-08-29 12:45
閱讀 3007·2019-08-29 12:26
閱讀 2821·2019-08-28 17:51
