专栏首页阿伟的个人博客有序矩阵中第K小的元素

有序矩阵中第K小的元素

问题描述:

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

示例:

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

返回 13。


提示:
你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2 。


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解决方案

归并排序

利用其每一行都是递增的这一特性,我们可以知道当前最小的元素一定在所有行的第一个元素之中,因此一个做法为每次从每一行第一个元素中找到最小的元素删除他,如此进行k次,第k次删除的元素即为所求。若直接进行这种做法时间复杂度为O(k * N),其中N为矩阵的边长,需要找k次每次需要遍历一遍矩阵的一列。

因此我们想到可以使用一个小根堆来优化找最小值的过程,堆的初值为将第一列元素存进去,每次从堆中弹出一个元素,弹出的是哪一行的就把那行当前位置元素存入堆中。如此每次只需要O(logN)的时间复杂度总体时间复杂度为O(k * log(N))。

实现代码如下:

class Solution {
    public static class Node{
        int index;
        int val;
        public Node(int index, int val){
            this.index = index;
            this.val = val;
        }
    }
    public static class NodeComparator implements Comparator<Node>{
        public int compare(Node n1, Node n2){
            return n1.val - n2.val;
        }
    }
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int[] next = new int[n]; // next[i] 为第i行开始元素下标
        Queue<Node> minHeap = new PriorityQueue<>(new NodeComparator());
        for(int i = 0; i < n; i++){
            minHeap.add(new Node(i, matrix[i][next[i]++]));
        }
        int result = -1;
        while(k > 0){
            Node cur = minHeap.remove();
            k--;
            result = cur.val;
            if(next[cur.index] < n){
                minHeap.add(new Node(cur.index, matrix[cur.index][next[cur.index]++] ) );
            }    
        }
        return result;
    }
}

二分搜索

对值进行二分,下界为left = matrix[0] [0],上界为right = matrix[n - 1] [n - 1]。每次统计小于mid的数目记做count,

若count小于等于k则说明待求值在mid右侧(不包括mid),left = mid + 1;

若count大于k,则说明待求值在mid左侧(包括mid) ,right = mid。

此外对于如何统计小于mid的数目,可以从左下角的位置开始遍历,

若当前值小于等于mid,则证明其上的所有值都小于等于mid,统计数目并左移

若当前值大于mid,则证明该行从当前位置开始均大于mid,上移动。

时间复杂度为O(log(max- min)* N),其中max为矩阵中的最大值,min为矩阵中的最小值,N为矩阵的边长。实现代码如下:

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int left = matrix[0][0];
        int right = matrix[matrix.length - 1][matrix.length - 1];
        while(left < right){
            int mid = left + (right - left) / 2;
            int num = getNum(matrix, mid);
            if(num >= k){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
    public int getNum(int[][] matrix, int mid){ // 获得小于等于mid 的值的数目
        int count = 0;
        int i = matrix.length - 1;
        int j = 0;
        while(i >= 0 && j < matrix.length){
            if(matrix[i][j] <= mid){
                count += i + 1; // 一次计算一列的数目
                j++;
            }else{
                i--;
            }
        }
        return count;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 岛屿问题

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

    你的益达
  • 乘法表中第k小的数

    给定高度m 、宽度n 的一张 m * n的乘法表,以及正整数k,你需要返回表中第k 小的数字。

    你的益达
  • leetcode第197场周赛

    如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ,就可以认为这是一组 好数对 。

    你的益达
  • N(奇数)阶幻方-java实现代码

    看完最强大脑,有一期是说N阶幻立方的,作为一个程序员,我的第一反应时我可以用程序实现,在此公布N(奇数)阶幻方的java实现代码:

    lzugis
  • LeetCode 454. 四数相加 II(哈希)

    给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l]...

    Michael阿明
  • 跳槽必刷算法题系列(一)

    第74题:编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    程序员小浩
  • 1022 D进制的A+B (20 分)

    输入两个非负 10 进制整数 A 和 B (≤230−1),输出 A+B 的 D (1<D≤10)进制数。

    可爱见见
  • HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)

    话不多说,日常一水题,水水更健康!┗|`O′|┛ 嗷~~ a/b + c/d Time Limit: 1000/1000 MS (Java/Others)   ...

    Angel_Kitty
  • 2018年第九届蓝桥杯B组题解

    按着题目把这些数转换成8字节的二进制数就可以了,负数的二进制是补码。可以自己写个函数实现一下,实际效果图:

    Ch_Zaqdt
  • HDU 1875 畅通工程再续(kruskal)

    畅通工程再续 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券