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

q5iwbnjs 于 2023-02-11 发布在 Java

关注(0)|答案(4)|浏览(105)

因此，我正在处理一个leetcode问题，我的代码在某些情况下有效，但在某些情况下失败。
问题是这样的：
给定一个n x n矩阵，其中每行和列都按升序排序，求矩阵中第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

请注意，对于第一个输入，代码运行良好，其中二维数组中第8个最小的元素是13，但是对于第二个输入，代码返回2作为第一个最小的元素，而不是返回1。
有人能帮我修改代码吗？我请求你们不要实现一些花哨的速记排序技术，例如Arrays.sort ......这对我来说并不理想，因为我正在学习如何实现堆。非常感谢：）

Java

来源：https://stackoverflow.com/questions/64101949/kth-smallest-element-in-a-sorted-matrix

4条答案

按热度按时间

jgovgodb1#

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

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;
    }
}

赞(0）回复(0）举报 2023-02-11

ryoqjall2#

可以使用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();
}

赞(0）回复(0）举报 2023-02-11

gt0wga4j3#

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

赞(0）回复(0）举报 2023-02-11

z9zf31ra4#

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

赞(0）回复(0）举报 2023-02-11

我来回答

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

4条答案

相关问题

热门标签

最新问答