Kth più piccolo elemento nella matrice ordinata

Questa è una domanda di intervista.

Trovare il Kth più piccolo elemento in una matrice con gli ordinati in righe e colonne.
È corretto affermare che il Kth più piccolo elemento è uno dei a[i, j] come i + j = K ?

  • come è la matrice ordinata? solo che in ogni riga o colonna è il numero crescente?
  • Sì, i numeri in ogni riga e colonna sono ordinati in ordine crescente.
  • E ‘ molto facile a venire con un controesempio per dimostrare che l’affermazione è falsa.
  • la soluzione ovviamente non è corretto. es. primo elemento può essere trovato in un angolo, ma il secondo numero può essere uno dei due vicini di casa. il terzo può essere una delle 5 possibili indici. si devono impiegare qualche modifica di ricerca binaria.
InformationsquelleAutor Michael | 2013-03-02

 

7 Replies
  1. 35

    False.

    Considerare una matrice semplice come questo:

    1 3 5
    2 4 6
    7 8 9
    

    9 è il più grande (9 più piccolo elemento. Ma il 9 è a[3, 3] 3+3 != 9. (Non importa che cosa di indicizzazione convenzione, essa non può essere vero).


    È possibile risolvere questo problema in tempo O(k log n) tempo unendo le righe in modo incrementale, aumentata con un mucchio per trovare in modo efficiente il minimo elemento.

    In pratica, si mette gli elementi della prima colonna in un heap e traccia la riga da cui provengono. Ad ogni passo, è possibile rimuovere l’elemento minima dal mucchio e spingere il prossimo elemento della riga di provenienza, ovvero se si raggiunge la fine della riga, quindi non spingere nulla). Sia per la rimozione che il minimo e l’aggiunta di un nuovo elemento di costo O(log n). A-esimo passo, è necessario rimuovere il jesimo elemento più piccolo, così dopo k passi che si sono fatti per un costo totale di O(k log n) operazioni (dove n è il numero di righe della matrice).

    Per la matrice di cui sopra, è inizialmente iniziare con 1,2,7 nell’heap. Si rimuovere 1 e aggiungere 3 (dato che la prima riga è 1 3 5) per ottenere 2,3,7. Si rimuovere 2 e aggiungere 4 per ottenere 3,4,7. Rimuovere 3 e aggiungere 5 per ottenere 4,5,7. Rimuovere 4 e aggiungere 6 per ottenere 5,6,7. Nota che ci sono la rimozione di elementi in tutto il mondo ordinato. Si può vedere che continuando questo processo produrrà il kesimo elemento più piccolo dopo k iterazioni.

    (Se la matrice ha più righe che colonne, utilizzare le colonne invece di ridurre il tempo di esecuzione.)

    • che è Buono..dare un esempio, quando la matrice è un insieme. Nessuna ripetizione di elementi
    • molto banale, fatto.
    • Si prega di controllare la mia risposta Se ho fatto correggere. Con la mia ipotesi
    • bene, con questo presupposto è giusto. Ma l’ipotesi è troppo restrittiva.
    • Vedere la mia nuova matrice. Questo è ordinati per righe e colonne, ma la tua soluzione non funziona per questo.
    • OK molto bello!! E la mia soluzione non funziona per questo. ma non posso dare 2 come, da considerare in sospeso…:)
    • Che è bello. Grazie ! Ora ho capito 🙂
    • Invece di avere un heap di dimensione n, possiamo prendere di dimensione k, e spingere primi k elementi di primo coulumn in esso, e poi proseguire come sopra. Che ci potesse dare una complessità di O(k log k).
    • Questa soluzione funziona meglio se solo la riga o la colonna è ordinata (essenzialmente, si tratta di n-vie di unione esterno ordinamento). @user1987143 è meglio dato che si sfrutta il fatto che sia di riga e di colonna sono ordinati.
    • Hai definito numero di righe n, quindi se si inizializza il vostro min heap con la prima colonna, non il runtime n + k log (n) ? (Lei non sembra essere considerando che l’inizializzazione fase di runtime di calcolo).

  2. 24

    O(k log(k)) soluzione.

    • Costruire un minheap.

    • Aggiungere (0,0) per l’heap. Mentre, non abbiamo trovato il kth più piccolo elemento, rimuovere il primo elemento (x,y) dal mucchio e aggiungere prossimi due elementi [(x+1,y) e (x,y+1)] se non è stato visitato prima.

    Stiamo facendo O(k) operazioni su un heap di dimensione O(k) e, di conseguenza, la complessità.

    • Si può dare a questo un po ‘ di formattazione? un po ‘ difficile da leggere così com’è
    • Sei sicuro che questo è corretto? Voglio dire, anche io penso la stessa cosa, solo stupiti per il numero di voti ricevuto la vostra risposta in contrasto con l’altra, anche se la complessità della soluzione è migliore rispetto agli altri.
    • Credo che questo sia corretto, è possibile che qualcuno esperto, si prega di confermare ?
    • credo che questo sia corretto e che il runtime è meglio che il accettato di rispondere.
    • Non è sicuro se sia meglio di O(klog(n)) come 0 <= k <= n^2 e k ha n-1/n probabilità di essere superiore a n
    • beh, può anche essere scritto come O(n log(n)) allora. O(k log(k)) è più preciso, nel mio punto di vista. (se n è il numero di elementi nella matrice)
    • D’accordo che la complessità è O(k log (k)). Ruvida spiegazione: Heap pop complessità è O(log(heapsize)). Qui di dimensione heap inizia da 1 e cresce, uno per uno, k, k iterazioni. Heapsize cresce di una unità in ogni iterazione (per la maggior parte delle iterazioni) perché in ogni fase di un elemento viene rimosso e due, cioè a destra e giù per le celle sono aggiunte. (Tranne che nei bordi della matrice) di Modo, di tempo, di complessità ~= O(log(1)) + O(log(2)) + …. O(log(k)) ~= k log(k)
    • Non abbiamo bisogno di mantenere i nodi visitati al fine di evitare la duplicazione?

  3. 1

    Inizio che attraversano la matrice dall’angolo in alto a sinistra (0,0) e utilizzare un heap binario per la memorizzazione di “frontiera” – un confine tra visitato parte della matrice e tutto il resto.

    Implementazione in Java:

    private static class Cell implements Comparable<Cell> {
    
        private final int x;
        private final int y;
        private final int value;
    
        public Cell(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    
        @Override
        public int compareTo(Cell that) {
            return this.value - that.value;
        }
    
    }
    
    private static int findMin(int[][] matrix, int k) {
    
        int min = matrix[0][0];
    
        PriorityQueue<Cell> frontier = new PriorityQueue<>();
        frontier.add(new Cell(0, 0, min));
    
        while (k > 1) {
    
            Cell poll = frontier.remove();
    
            if (poll.y + 1 < matrix[poll.x].length) frontier.add(new Cell(poll.x, poll.y + 1, matrix[poll.x][poll.y + 1]));
            if (poll.x + 1 < matrix.length) frontier.add(new Cell(poll.x + 1, poll.y, matrix[poll.x + 1][poll.y]));
    
            if (poll.value > min) {
                min = poll.value;
                k--;
            }
    
        }
    
        return min;
    
    }
    
  4. 0

    Sembra che questo utilizza solo la funzione: ogni riga è ordinato, ma non usare la sua colonna-saggi ordinati in funzione.

  5. 0

    Come persone menzionate in precedenza, il modo più semplice è quello di costruire un min heap. Ecco una implementazione Java utilizzando PriorityQueue:

    private int kthSmallestUsingHeap(int[][] matrix, int k) {
    
        int n = matrix.length;
    
        //This is not necessary since this is the default Int comparator behavior
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        };
    
        //building a minHeap
        PriorityQueue<Integer> pq = new PriorityQueue<>(n*n, comparator);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                pq.add(matrix[i][j]);
            }
        }
    
        int ans = -1;
        //remove the min element k times
        for (int i = 0; i < k; i++) {
            ans = pq.poll();
        }
    
        return ans;
    }
    
  6. 0

    Kth più piccolo elemento della matrice :

    Il problema può essere ridotto come di seguito.

    se k è 20, quindi prendere k*k matrice (risposta sarà sicuramente mentire).

    Ora è possibile unire le righe in coppia ripetutamente per costruire un array ordinato e poi trovare il kth numero più piccolo.

  7. -1
    //int arr[][] = {{1, 5, 10, 14},
    //       {2, 7, 12, 16},
    //       {4, 10, 15, 20},
    //       {6, 13, 19, 22}
    //};
    //O(k) Solution
    public static int myKthElement(int arr[][], int k) {
        int lRow = 1;
        int lCol = 0;
        int rRow = 0;
        int rCol = 1;
        int count = 1;
    
        int row = 0;
        int col = 0;
    
        if (k == 1) {
            return arr[row][col];
        }
    
        int n = arr.length;
        if (k > n * n) {
            return -1;
        }
    
        while (count < k) {
            count++;
    
            if (arr[lRow][lCol] < arr[rRow][rCol]) {
                row = lRow;
                col = lCol;
    
                if (lRow < n - 1) {
                    lRow++;
                } else {
                    if (lCol < n - 1) {
                        lCol++;
                    }
    
                    if (rRow < n - 1) {
                        lRow = rRow + 1;
                    }
                }
            } else {
                row = rRow;
                col = rCol;
    
                if (rCol < n - 1) {
                    rCol++;
                } else {
                    if (rRow < n - 1) {
                        rRow++;
                    }
                    if (lCol < n - 1) {
                        rCol = lCol + 1;
                    }
                }
            }
        }
    
        return arr[row][col];
    }
    
    • Si prega di aggiungere alcuni contenuti alla tua risposta, per elaborare il vostro approccio o una soluzione, oltre al codice in modo da rendere meglio l’idea a chi sta attraversando le risposte.

Lascia un commento