378. Kth Smallest Element in a Sorted Matrix

Y3G 發布于2019-08-14 17:28 / 3424人閱讀

摘要：復雜度是，其中。這做法和異曲同工。看了網上給的解法，沒有二分，二分的是結果。每次找到一個，然后求比它小的元素的個數，根據個數大于還是小于來二分。參考算的時候可以優化

378. Kth Smallest Element in a Sorted Matrix

題目鏈接：https://leetcode.com/problems...

求矩陣里面第k小的數，首先比較容易想到的是用heap來做，maxheap或者minheap都可以，用maxheap的話把全部元素放進heap里面，同時如果heap的size大于k就彈出，保持heap的size為k，最后root的元素就是第k小的。復雜度是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/...
由于矩陣是有序的，我們知道每一行右邊的元素總是大于左邊，下面的元素總是大于上面的。所以先把第一行放進去，然后每次增加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];
    }
}

標簽還寫了binary search，如果二分index的話，每次找到midx和midy之后，之后index很難表示出來。看了網上給的解法，沒有二分index，二分的是結果。每次找到一個mid，然后求比它小的元素的個數，根據個數大于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的時候可以優化：

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;
    }
}

云服務器 GPU云服務器 Kth Smallest Matrix modelview matrix

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66654.html

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 2019-08-14 18:13 評論0 收藏0
[LeetCode] 378. Kth Smallest Element in a Sorted M

摘要：先放一行，或一列把堆頂的最小元素取出來，取次，如果該有下一行下一列的，放入堆中最小的個元素已經在上面的循環被完了，下一個堆頂元素就是 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 2019-08-16 13:43 評論0 收藏0
leetcode378. Kth Smallest Element in a Sorted Matr

摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構成第個元素的值進行堆排序就可以了。題目要求 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 2019-08-16 15:05 評論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 2019-08-14 15:45 評論0 收藏0
[Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節

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

Dean 2019-08-14 12:26 評論0 收藏0