成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

378. Kth Smallest Element in a Sorted Matrix

makeFoxPlay / 2300人閱讀 

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.
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13
public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue pq = new PriorityQueue<>(new Comparator(){
            public int compare(int[] a, int[] b){
                return a[2] - b[2];
            }
        });
        
        int n = matrix.length;
        // add first row
        for(int i=0; i< n; i++){
            pq.offer(new int[]{0, i, matrix[0][i]});
        }
        
        for(int i=0; i

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int lo = matrix[0][0],  hi = matrix[m-1][n-1];
        while(lo < hi){
            int mid = lo + (hi-lo)/2;
            int count = 0, j = n -1;
            for(int i=0; i=0 && matrix[i][j] > mid) j--;
                // count those <= mid
                count += j+1;
            }
            // if count < k, the number is smaller
            if(count < k) lo = mid+1;
            else hi = mid;
        }
        return lo;
    }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67070.html

相關(guān)文章

  • [LeetCode] 378. Kth Smallest Element in a Sorted M

    摘要：先放一行，或一列把堆頂?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...

    Shihira 評論0 收藏0

  • 378. Kth Smallest Element in a Sorted Matrix

    摘要：復(fù)雜度是，其中。這做法和異曲同工?？戳司W(wǎng)上給的解法，沒有二分，二分的是結(jié)果。每次找到一個，然后求比它小的元素的個數(shù)，根據(jù)個數(shù)大于還是小于來二分。參考算的時候可以優(yōu)化 378. Kth Smallest Element in a Sorted Matrix 題目鏈接：https://leetcode.com/problems... 求矩陣里面第k小的數(shù)，首先比較容易想到的是用heap來做...

    Y3G 評論0 收藏0

  • leetcode378. Kth Smallest Element in a Sorted Matr

    摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第個元素的值進行堆排序就可以了。 題目要求 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...

    dailybird 評論0 收藏0

  • [LintCode] Kth Smallest Number in Sorted Matrix

    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...

    mgckid 評論0 收藏0

  • [Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節(jié)

    摘要：中序遍歷復(fù)雜度時間空間思路因為左節(jié)點小于根節(jié)點小于右節(jié)點，二叉搜索樹的一個特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

    Dean 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<