Kth plus petit élément d'une matrice triée

Question

Je travaille donc sur une question Leetcode et mon code fonctionne dans certains cas mais échoue dans certains cas.

Voici la question:

Étant donné une n x nmatrice où chacune des lignes et colonnes est triée par ordre croissant, trouvez le kème élément le plus petit de la matrice.

Notez qu'il s'agit du kième élément le plus petit dans l'ordre trié, et non du kième élément distinct.

Exemple:

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

retour: 13

Mon approche consiste à utiliser un minHeap, même s'il indiquait que le tableau est trié, j'avais encore besoin de m'assurer que je l'ai trié de la valeur la plus faible à la plus grande.

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

Voici mes entrées:

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

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

Voici les sorties:

Output 1: 13
Output 2: 2

Notez que le code fonctionne très bien pour ma première entrée où le 8e plus petit élément du 2d-array est 13, mais pour la deuxième entrée, le code renvoie 2 comme premier plus petit élément plutôt que 1.

Quelqu'un peut-il m'aider s'il vous plaît à corriger le code? Je vous demande de ne pas implémenter une technique de tri sténographique sophistiquée, par exemple Arrays.sort ... ce n'est pas idéal pour moi car j'essaie d'apprendre à implémenter des tas. Merci beaucoup :)

Answer 1

Pour résoudre ce problème, nous pouvons également effectuer une recherche binaire (un peu plus efficace):

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

Vous pouvez utiliser la flatMapToIntméthode pour parcourir les lignes d'un tableau 2D dans un flux:

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