378. Kth Smallest Element in a Sorted Matrix

Y3G 发布于2019-08-14 17:28 / 3404人阅读

摘要：复杂度是，其中。这做法和异曲同工。看了网上给的解法，没有二分，二分的是结果。每次找到一个，然后求比它小的元素的个数，根据个数大于还是小于来二分。参考算的时候可以优化

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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