亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專(zhuān)欄INFORMATION COLUMN

378. Kth Smallest Element in a Sorted Matrix

Y3G / 3476人閱讀

摘要：復(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)做，maxheap或者minheap都可以，用maxheap的話把全部元素放進(jìn)heap里面，同時(shí)如果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里面有個(gè)比較有意思的heap做法：
https://discuss.leetcode.com/...
由于矩陣是有序的，我們知道每一行右邊的元素總是大于左邊，下面的元素總是大于上面的。所以先把第一行放進(jìn)去，然后每次增加row的值，這樣可以比較matrixrow和matrixrow+1哪個(gè)小，poll出小的那個(gè)。這做法和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)簽還寫(xiě)了binary search，如果二分index的話，每次找到midx和midy之后，之后index很難表示出來(lái)?？戳司W(wǎng)上給的解法，沒(méi)有二分index，二分的是結(jié)果。每次找到一個(gè)mid，然后求比它小的元素的個(gè)數(shù)，根據(jù)個(gè)數(shù)大于k還是小于k來(lái)二分。參考：
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的時(shí)候可以?xún)?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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66654.html

相關(guān)文章

  • 378. Kth Smallest Element in a Sorted Matrix

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

    makeFoxPlay 評(píng)論0 收藏0

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

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

    Shihira 評(píng)論0 收藏0

  • leetcode378. Kth Smallest Element in a Sorted Matr

    摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(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...

    dailybird 評(píng)論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 評(píng)論0 收藏0

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

    摘要：中序遍歷復(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...

    Dean 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<