leetcode378. Kth Smallest Element in a Sorted Matr

dailybird 发布于2019-08-16 15:05 / 2536人阅读

摘要：因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第个元素的值进行堆排序就可以了。

题目要求

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.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.
Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

在一个从左到右，从上到下均有序的二维数组中，找到从小到第k个数字，这里需要注意，不要求一定要是唯一的值，即假设存在这样一个序列1,2,2,3，则第三个数字是2而不是3。

思路一：优先队列

当涉及到从一个集合中查找一个元素这样的问题时，我们往往会立刻想到查找的几种方式：有序数组查找，无序数组查找，堆排序。这里如果将二维数组转化为一维有序数组，成本未免太大了。同理，将其中所有元素都转化为堆，也会存在内存不足的问题。因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第k个元素的值进行堆排序就可以了。

    public int kthSmallest(int[][] matrix, int k) {
        //优先队列
        PriorityQueue queue = new PriorityQueue();
        //将每一行的第一个元素放入优先队列中
        for(int i = 0 ; i{
        int x;
        int y;
        int value;
        
        public Tuple(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
        @Override
        public int compareTo(Tuple o) {
            // TODO Auto-generated method stub
            return this.value - o.value;
        }
    }

思路二：二分法查找

二分查找的核心问题在于，如何找到查找的上界和下届。这边我们可以矩阵中的最大值和最小值作为上界和下界。然后不停的与中间值进行比较，判断当前矩阵中小于该中间值的元素有几个，如果数量不足k，就将左指针右移，否则，就将右指针左移。直到左右指针相遇。这里需要注意，不能在数量等于k的时候就返回mid值，因为mid值不一定在矩阵中存在。

    public int kthSmallest2(int[][] matrix, int k){
        int low = matrix[0][0], high = matrix[matrix.length-1][matrix[0].length-1];
        while(low <= high) {
            int mid = low + (high - low) / 2;
            int count = 0;
            int i = matrix.length-1 , j = 0;
            //自矩阵左下角开始计算比mid小的数字的个数
            while(i>=0 && j < matrix.length){
                if(matrix[i][j]>mid) i--;
                else{
                    count+=i+1;
                    j++;
                }
            }
            if(count < k) {
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return low;
    }

GPU云服务器云服务器 Kth Smallest Sorted Element

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

转载请注明本文地址：https://www.ucloud.cn/yun/73264.html

[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
378. Kth Smallest Element in a Sorted Matrix

摘要：复杂度是，其中。这做法和异曲同工。看了网上给的解法，没有二分，二分的是结果。每次找到一个，然后求比它小的元素的个数，根据个数大于还是小于来二分。参考算的时候可以优化 378. Kth Smallest Element in a Sorted Matrix 题目链接：https://leetcode.com/problems... 求矩阵里面第k小的数，首先比较容易想到的是用heap来做...

Y3G 2019-08-14 17:28 评论0 收藏0
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] 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
[Leetcode-Tree] Kth Smallest Element in a BST

摘要：解题思路本题需要找的是第小的节点值，而二叉搜索树的中序遍历正好是数值从小到大排序的，那么这题就和中序遍历一个情况。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

Carl 2019-08-16 10:26 评论0 收藏0