排序矩阵中的k个最小元素

Question

所以我正在研究一个Leetcode问题，我的代码在某些情况下有效，但在某些情况下失败。

问题是：

给定一个nxn矩阵，其中每个行和列都按升序排序，找出矩阵中第k个最小的元素。

请注意，它是排序顺序中的第k个最小元素，而不是第k个独立元素。

例子：

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

返回： 13

我的方法是使用minHeap，即使它声明数组已经排序，我仍然需要确保我已经将它从最小值排序到最大值。

这是我的代码：

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int result = 0;

        HashMap<Integer, Integer> map = new HashMap<>();
        //populate HashMap 
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                map.put(matrix[i][j],
                        map.getOrDefault(matrix[i][j], 0) + 1);
            }
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq =
                new PriorityQueue<>((n1, n2) -> n1.getValue() - n2.getValue());

        pq.addAll(map.entrySet());

        for (int i = 0; i < k && !(pq.isEmpty()); i++) {
            result = pq.poll().getKey();
        }

        return result;
    }
}

以下是我的意见：

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

Input 2: [[1,2],[1,3]] 
k = 1 

以下是输出：

Output 1: 13
Output 2: 2

请注意，对于我的第一个输入，2d数组中第8个最小的元素是13，代码工作正常，但是对于第二个输入，代码返回2作为我的第一个最小元素，而不是返回1。

有人能帮我修复代码吗？我请求你不要实现一些花哨的速记排序技术，例如rrays.sort....这对我来说并不理想，因为我正在努力学习如何实现堆。谢谢：）

Answer 1

public static int kthSmallest(int[][] matrix, int k) {
    return Arrays
            .stream(matrix)
            .flatMapToInt(x -> Arrays.stream(x))
            .sorted()
            .skip(k-1)
            .findFirst()
            .getAsInt();
}

Answer 2

可以使用flatMapToInt方法在一个流中迭代二维数组的行：

public static void main(String[] args) {
    int[][] matrix1 = {{1, 5, 9}, {10, 11, 13}, {12, 13, 15}};
    int[][] matrix2 = {{1, 2}, {1, 3}};

    System.out.println(kthSmallest(matrix1, 8)); // 13
    System.out.println(kthSmallest(matrix2, 1)); // 1
}

public static int kthSmallest(int[][] matrix, int k) {
    return Arrays.stream(matrix)
            .flatMapToInt(Arrays::stream)
            .skip(k - 1)
            .findFirst()
            .getAsInt();
}

Answer 3

为了解决这个问题，我们也可以二进制搜索（更有效一点）：

public class Solution {
    public static final int kthSmallest(final int[][] matrix, final int k) {
        int lo = matrix[0][0];
        int hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;

        while (lo < hi) {
            final int mid = lo + (hi - lo) / 2;
            int count = 0;
            int col = matrix[0].length - 1;

            for (int row = 0; row < matrix.length; ++row) {
                while (col >= 0 && matrix[row][col] > mid) {
                    col--;
                }
                count += (col + 1);
            }
            if (count < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}