Kth Kleinstes Element in einer sortierten Matrix

Question

Ich arbeite also an einer Leetcode-Frage und mein Code funktioniert in einigen Fällen, schlägt jedoch in bestimmten Fällen fehl.

Hier ist die Frage:

Suchen Sie bei einer gegebenen n x nMatrix, in der jede der Zeilen und Spalten in aufsteigender Reihenfolge sortiert ist, das k-te kleinste Element in der Matrix.

Beachten Sie, dass es das k-te kleinste Element in der sortierten Reihenfolge ist, nicht das k-te unterschiedliche Element.

Beispiel:

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

Rückkehr: 13

Mein Ansatz ist die Verwendung von minHeap, auch wenn angegeben wurde, dass das Array sortiert ist. Ich musste dennoch sicherstellen, dass es vom kleinsten zum größten Wert sortiert ist.

Hier ist mein Code:

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

Hier sind meine Eingaben:

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

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

Hier sind die Ausgänge:

Output 1: 13
Output 2: 2

Beachten Sie, dass der Code für meine erste Eingabe, bei der das achtkleinste Element im 2d-Array 13 ist, einwandfrei funktioniert. Für die zweite Eingabe gibt der Code jedoch 2 als mein erstes kleinstes Element zurück, anstatt 1 zurückzugeben.

Kann mir bitte jemand helfen, den Code zu reparieren? Ich bitte Sie, keine ausgefallene Kurzsortiertechnik zu implementieren, z. B. Arrays.sort ... es ist nicht ideal für mich, da ich versuche zu lernen, wie man Heaps implementiert. Vielen Dank :)

Answer 1

Um dieses Problem zu lösen, können wir auch eine binäre Suche durchführen (etwas effizienter):

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

Answer 2

Mit der flatMapToIntMethode können Sie die Zeilen eines 2D-Arrays in einem Stream durchlaufen:

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