有序矩阵中第K小的元素

你的益达

发布于 2020-08-05 15:36:59

5560

发布于 2020-08-05 15:36:59

问题描述：

给定一个 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;
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-07-02，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度