LeetCode刷题笔记2:有序矩阵中第K小的元素

作者 : 开心源码 本文共2265个字,预计阅读时间需要6分钟 发布时间: 2022-05-13 共242人阅读

题目形容:

给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。

难度:中等

示例:

matrix = [ 

                [ 1,  5,  9], 

                [10, 11, 13],

                [12, 13, 15]

],

k = 8,

返回 13。 

链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix

看到这个题,我首先就想到了优先队列。在查找第k个大小的元素时,小顶堆是一个非常不错的选择。Java自带的小顶堆为PriorityQueue,也就是优先队列。先将所有数组中所有元素放入栈中,而后从小顶堆中弹出k个元素就可,第k个元素即为答案。

public static int kthSmallest(int[][] matrix, int k) {

        //维护一个小顶堆,而后弹出K个元素

        Queue queue =new PriorityQueue<>();

        for (int i =0; i < matrix.length; i++)

                for (int j =0; j < matrix.length; j++) {

                        queue.add(matrix[i][j]);

                }

        while (k >1) {

                queue.poll();

                k–;

        }

        return queue.poll();

}

优先队列的插入和删除操作时间复杂度为logn,所以总的时间复杂度为O(n*n*logn)

然而这种解法没有利用到题目所给到的矩阵的特性。所以尽管写起来简单,但时间复杂度实在是难以让人满意。

所以我们要充分利用这个矩阵的特性。我们可以从矩阵的最大值max与最小值min之间取一个数mid。而后从矩阵左下角出发,当matrix[i][j]小于等于mid则说明第j列i行以上的元素都小于等于mid.统计下这些元素的个数num。而后将j+1,即右移一步。若matrix[i][j]大于mid,则第i行第j列右边的元素也都大于mid,这些大于mid的元素就不需要记录了,这个时候我们需要向上走一步使得i-1,这样当前的matrix[i][j]更小。直到统计完所有小于等于mid的数。

当然,我们其实也可以从矩阵的右上角出发,matrix[i][j]小于等于mid则说明第i行j列左边的的元素都小于等于mid.之后的操作尽管不一样,但是核心思想是一样的,记录下小于等于mid的数就可

若是num>=k则说明此时mid的大小不小于答案answer。即此时mid>=answer.

若是num<k则说明此时mid的大小大于答案answer,即mid<answer.

对于mid>=answer的情况我们需要将min减小,对于mid<answer的情况则需要使得mid增大

public static int kthSmallest2(int[][] matrix, int k) {

            //每次选取一个处于max与min之间的数mid,而后从左下角出发,计算比它小的数字              num。

            //若num>=k则减小mid的值,反之则缩小

            int min = matrix[0][0];

            int max = matrix[matrix.length -1][matrix.length -1];

            while (min < max) {

                    int mid = ((max – min) >>1) + min;

                    if (countSmaller(matrix, mid) >= k) {

                                max = mid;//不能写mid-1,当mid恰好等于ans时,这样的操作会使得正确的ans被跳过,导致计算出的结果偏小。

                    }else {

                              min = mid +1;

                    }

        }

        return min;

}

private static int countSmaller(int[][] matrix, int mid) {

        int num =0;

        int i = matrix.length -1;

        int j =0;

        while (i >=0 && j < matrix.length) {

                    if (matrix[i][j] <=mid) {//若matrix[i][j]小于等于mid则说明第j列i行以上的元素都小于等于mid

                            j++;

                            num += i +1;

                    }else {//若matrix[i][j]大于mid,则第i行第j列右边的元素也都大于mid,所以不需要累加num

                            i–;

                    }

        }

        return num;

}

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode刷题笔记2:有序矩阵中第K小的元素

发表回复