資訊專欄INFORMATION COLUMN
摘要：復(fù)雜度是，其中。這做法和異曲同工。看了網(wǎng)上給的解法，沒有二分，二分的是結(jié)果。每次找到一個，然后求比它小的元素的個數(shù)，根據(jù)個數(shù)大于還是小于來二分。參考算的時候可以優(yōu)化
378. Kth Smallest Element in a Sorted Matrix
題目鏈接：https://leetcode.com/problems...
求矩陣?yán)锩娴趉小的數(shù)，首先比較容易想到的是用heap來做，maxheap或者minheap都可以，用maxheap的話把全部元素放進(jìn)heap里面，同時如果heap的size大于k就彈出，保持heap的size為k，最后root的元素就是第k小的。復(fù)雜度是k + (m*n - k)logk，其中m = matrix.length, n = matrix[0].length。
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
// heap
PriorityQueue maxHeap = new PriorityQueue<>(k + 1, (a, b) -> b - a);
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
maxHeap.offer(matrix[i][j]);
if(maxHeap.size() > k) maxHeap.poll();
}
}
return maxHeap.poll();
}
}
看discussion里面有個比較有意思的heap做法：
https://discuss.leetcode.com/...
由于矩陣是有序的，我們知道每一行右邊的元素總是大于左邊，下面的元素總是大于上面的。所以先把第一行放進(jìn)去，然后每次增加row的值，這樣可以比較matrixrow和matrixrow+1哪個小，poll出小的那個。這做法和Find K Pairs with Smallest Sums異曲同工。
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
// heap
PriorityQueue minHeap = new PriorityQueue<>(k+1, (a, b) -> a[2] - b[2]);
for(int j = 0; j < Math.min(k, matrix[0].length); j++) {
minHeap.offer(new int[] {0, j, matrix[0][j]});
}
// for k loop find the result
for(int i = 0; i < k-1; i++) {
int[] cur = minHeap.poll();
if(cur[0] + 1 < matrix.length) {
minHeap.offer(new int[] {cur[0] + 1, cur[1], matrix[cur[0] + 1][cur[1]]});
}
}
return minHeap.poll()[2];
}
}
標(biāo)簽還寫了binary search，如果二分index的話，每次找到midx和midy之后，之后index很難表示出來?？戳司W(wǎng)上給的解法，沒有二分index，二分的是結(jié)果。每次找到一個mid，然后求比它小的元素的個數(shù)，根據(jù)個數(shù)大于k還是小于k來二分。參考：
http://bookshadow.com/weblog/...
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
// binary search
int n = matrix.length;
int l = matrix[0][0], r = matrix[n-1][n-1];
while(l + 1 < r) {
int mid = l + (r - l) / 2;
int num = count(matrix, mid);
if(num >= k) r = mid;
else l = mid;
}
if(count(matrix, r) <= k - 1) return r;
return l;
}
private int count(int[][] matrix, int target) {
int n = matrix.length;
int result = 0;
for(int i = 0; i < n; i++) {
int j = 0;
while(j < n && matrix[i][j] < target) j++;
result += j;
}
return result;
}
}
算count的時候可以優(yōu)化：
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
// binary search
int n = matrix.length;
int l = matrix[0][0], r = matrix[n-1][n-1];
while(l + 1 < r) {
int mid = l + (r - l) / 2;
int num = count(matrix, mid);
if(num >= k) r = mid;
else l = mid;
}
if(count(matrix, r) <= k - 1) return r;
return l;
}
private int count(int[][] matrix, int target) {
int n = matrix.length;
int result = 0;
int i = n - 1, j = 0;
while(i >= 0 && j < n) {
if(matrix[i][j] < target) {
result += i + 1;
j++;
}
else i--;
}
return result;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66654.html
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...
摘要：先放一行，或一列把堆頂?shù)淖钚≡厝〕鰜恚〈危绻撚邢乱恍邢乱涣械模湃攵阎凶钚〉膫€元素已經(jīng)在上面的循環(huán)被完了，下一個堆頂元素就是 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...
摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第個元素的值進(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...
Problem Find the kth smallest number in at row and column sorted matrix. Example Given k = 4 and a matrix: [ [1 ,5 ,7], [3 ,7 ,8], [4 ,8 ,9], ] return 5 Challenge O(k log n), n is the maximal n...
摘要：中序遍歷復(fù)雜度時間空間思路因為左節(jié)點小于根節(jié)點小于右節(jié)點，二叉搜索樹的一個特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...
閱讀 2701·2021-10-12 10:12
閱讀 2341·2021-09-02 15:41
閱讀 2573·2019-08-30 15:55
閱讀 1404·2019-08-30 13:05
閱讀 2440·2019-08-29 11:21
閱讀 3539·2019-08-28 17:53
閱讀 3033·2019-08-26 13:39
閱讀 806·2019-08-26 11:50
