脚本宝典收集整理的这篇文章主要介绍了

[LeetCode] 378. Kth Smallest Element in a Sorted Matrix

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

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 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 ≤ n^2.

Solution

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        Queue<Node> queue = new PriorityQueue<Node>((a, b)->a.val-b.val);
        //先放一行,或一列
        for (int i = 0; i < n; i++) queue.offer(new Node(i, 0, matrix[i][0]));
        //把堆顶的最小元素取出来,取k-1次,如果该node有下一行/下一列的node,放入堆中
        for (int i = 0; i < k-1; i++) {
            Node node = queue.poll();
            if (node.y == n-1) continue;
            else queue.offer(new Node(node.x, node.y+1, matrix[node.x][node.y+1]));
        }
        //最小的k-1个元素已经在上面的for循环被poll完了,下一个堆顶元素就是kth smallest
        return queue.poll().val;
    }
}

class Node {
    int x;
    int y;
    int val;
    public Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

总结

以上是脚本宝典为你收集整理的

[LeetCode] 378. Kth Smallest Element in a Sorted Matrix

全部内容,希望文章能够帮你解决

[LeetCode] 378. Kth Smallest Element in a Sorted Matrix

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过