LeetCode 378. 有序矩阵中第K小的元素 Java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 378. 有序矩阵中第K小的元素 Java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含791字，纯文字阅读大概需要2分钟。

内容图文

容易想到的暴力解法：把数据都取出来排序，需要n2大小的数组存储

既然数组是有序的，把每一行看成一个有序数组，对这些数组进行归并排序，归并到第k个数为止。
看了题解，了解到优先级队列PriorityQueue可以用于实现归并排序，PriorityQueue底层是一个堆的结构。具体可参考这篇文章 刷算法不知道PriorityQueue?看了这篇文章才知道他有多实用

还有一种二分查找的算法，感觉不太容易想出。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int a[],int b[]){
                return a[0] - b[0];
            }
        });
        int n = matrix.length;
        for(int i=0;i<n;i++){
            pq.offer(new int[]{matrix[i][0],i,0});
        }
        for(int i=0;i<k-1;i++){
            int []now = pq.poll();
            if(now[2] != n-1){
                pq.offer(new int[]{matrix[now[1]][now[2]+1],now[1],now[2]+1});
            }
        }
        return pq.poll()[0];
    }
}

内容总结

以上是互联网集市为您收集整理的LeetCode 378. 有序矩阵中第K小的元素 Java全部内容，希望文章能够帮你解决LeetCode 378. 有序矩阵中第K小的元素 Java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端