[LintCode] Kth Smallest Number in Sorted Matrix

mgckid 发布于2019-08-14 15:45 / 2027人阅读

Problem

Find the kth smallest number in at row and column sorted matrix.

Example

Given k = 4 and a matrix:

[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]

return 5

Challenge

O(k log n), n is the maximal number in width and height.

Note Solution

I. Muggle (95% ac, last case exceeded time limit)

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int size = matrix.length * matrix[0].length;
        if (matrix == null) return 0;
        PriorityQueue queue = new PriorityQueue(size+1);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                queue.add(matrix[i][j]);
            }
        }
        for (int i = 1; i < k; i++) {
            queue.remove();
        }
        return queue.peek();
    }
}

II. 堆排序

public class Solution {
    public int kthSmallest(final int[][] matrix, int k) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        PriorityQueue heap = new PriorityQueue(k, new Comparator(){
            public int compare(int[] a, int[] b) {
                return Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]);
            }
        });
        heap.add(new int[]{0,0});
        visited[0][0] = true;
        while (k > 1) {
            int[] res = heap.remove();
            int x = res[0];
            int y = res[1];
            if (x+1 < matrix.length && visited[x+1][y] == false) {
                visited[x+1][y] = true;
                heap.add(new int[]{x+1, y});
            }
            if (y+1 < matrix[0].length && visited[x][y+1] == false) {
                visited[x][y+1] = true;
                heap.add(new int[]{x, y+1});
            }
            k--;
        }
        int[] res = heap.remove();
        return matrix[res[0]][res[1]];
    }
}

云服务器 GPU云服务器 Kth Smallest Matrix LintCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65991.html

378. Kth Smallest Element in a Sorted Matrix

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...

makeFoxPlay 2019-08-14 18:13 评论0 收藏0
[LeetCode] 378. Kth Smallest Element in a Sorted M

摘要：先放一行，或一列把堆顶的最小元素取出来，取次，如果该有下一行下一列的，放入堆中最小的个元素已经在上面的循环被完了，下一个堆顶元素就是 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...

Shihira 2019-08-16 13:43 评论0 收藏0
378. Kth Smallest Element in a Sorted Matrix

摘要：复杂度是，其中。这做法和异曲同工。看了网上给的解法，没有二分，二分的是结果。每次找到一个，然后求比它小的元素的个数，根据个数大于还是小于来二分。参考算的时候可以优化 378. Kth Smallest Element in a Sorted Matrix 题目链接：https://leetcode.com/problems... 求矩阵里面第k小的数，首先比较容易想到的是用heap来做...

Y3G 2019-08-14 17:28 评论0 收藏0
leetcode378. Kth Smallest Element in a Sorted Matr

摘要：因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第个元素的值进行堆排序就可以了。题目要求 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...

dailybird 2019-08-16 15:05 评论0 收藏0
[Leetcode-Tree] Kth Smallest Element in a BST

摘要：解题思路本题需要找的是第小的节点值，而二叉搜索树的中序遍历正好是数值从小到大排序的，那么这题就和中序遍历一个情况。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

Carl 2019-08-16 10:26 评论0 收藏0