Trovare il k più piccolo numero da n matrici ordinate

Quindi, hai n matrici ordinate (non necessariamente di uguale lunghezza), e devi restituire il kth più piccolo elemento nell’array combinato (cioè l’array combinato formato dall’unione di tutti gli n matrici ordinate)

Lo sto provando e le sue altre varianti da un po ‘di tempo, e fino ad ora mi sento a mio agio solo nel caso in cui ci siano due array di uguale lunghezza, entrambi ordinati e uno deve restituire la mediana di questi due. Questo ha una complessità temporale logaritmica.

Dopo questo ho cercato di generalizzarlo per trovare kth il più piccolo tra due array ordinati. Ecco la domanda su SO. Anche qui la soluzione data non è ovvia per me. Ma anche se in qualche modo riesco a convincermi di questa soluzione, sono ancora curioso di sapere come risolvere il caso generale assoluto (che è la mia domanda)

Qualcuno può spiegarmi una soluzione passo passo (che a mio parere dovrebbe prendere il tempo logaritmico cioè O (log (n 1 ) + log (n 2 ) … + log (n N ) dove n 1 , n 2 .. .n N sono le lunghezze dei n array) che partono dai casi più specifici e passano a quelli più generali?

So che domande simili per casi più specifici ci sono ovunque su Internet, ma non ho trovato una risposta convincente e chiara.

Ecco un link a una domanda (e la sua risposta) su SO che tratta di 5 array ordinati e trova la mediana della matrice combinata. La risposta diventa troppo complicata per me riuscire a generalizzarla.

Sono ben accetti anche approcci puliti per i casi più specifici (come ho detto durante il post).

PS: Pensi che questo possa essere ulteriormente generalizzato al caso di array non ordinati?

PPS: Non è un problema per i compiti a casa, mi sto solo preparando per le interviste.

Questo non generalizza i collegamenti, ma risolve il problema:

  1. Passa attraverso tutti gli array e, se qualcuno ha lunghezza> k, tronca alla lunghezza k (questo è sciocco, ma lo faremo con k più tardi, quindi fallo comunque)
  2. Identificare il più grande array rimanente A. Se più di uno, sceglierne uno.
  3. Scegli l’elemento centrale M della matrice più grande A.
  4. Utilizzare una ricerca binaria sugli array rimanenti per trovare lo stesso elemento (o l’elemento più grande <= M).
  5. In base agli indici dei vari elementi, calcolare il numero totale di elementi <= M e> M. Questo dovrebbe fornire due numeri: L, il numero <= M e G, il numero> M
  6. Se k
  7. Se k> L, troncare tutti gli array nei punti di divisione trovati e iterare sugli array più piccoli (utilizzare le metà superiori e cercare l’elemento (kL).

Quando arrivi al punto in cui hai un solo elemento per array (o 0), crea una nuova matrice di dimensione n con quei dati, ordina e scegli l’elemento kth.

Poiché sei sempre garantito di rimuovere almeno la metà di un array, in N iterazioni, ti libererai della metà degli elementi. Ciò significa che ci sono N log k iterazioni. Ogni iterazione è di ordine N log k (a causa delle ricerche binarie), quindi il tutto è N ^ 2 (log k) ^ 2 Questo è tutto, ovviamente, nel peggiore dei casi, basato sul presupposto che tu ti liberi solo della metà dell’array più grande, non degli altri array. In pratica, immagino che le prestazioni tipiche siano un po ‘migliori rispetto al caso peggiore.

Non può essere fatto in meno di tempo O(n) . Proof Sketch Se lo facesse, dovrebbe completamente non guardare almeno un array. Ovviamente, un array può cambiare arbitrariamente il valore dell’elemento kth .

Ho un O(n*log(n)*log(m)) relativamente semplice dove m è la lunghezza dell’array più lungo. Sono sicuro che è ansible essere leggermente più veloce, ma non molto più veloce.

Si consideri il caso semplice in cui si hanno n array ciascuno di lunghezza 1. Ovviamente, questo è isomorfo per trovare il k elemento in una lista non ordinata di lunghezza n . È ansible trovare questo in O(n) , vedere l’ algoritmo Mediana delle Medie, originariamente di Blum, Floyd, Pratt, Rivest e Tarjan , e non sono possibili algoritmi (asintoticamente) più veloci.

Ora il problema è come estendere questo a matrici ordinate più lunghe. Ecco l’algoritmo: trova la mediana di ogni matrice. Ordina l’elenco di tuple (median,length of array/2) e ordinalo per mediana. Cammina attraverso mantenendo una sum delle lunghezze, fino a raggiungere una sum maggiore di k. Ora hai una coppia di mediani, in modo tale che tu sappia che l’elemento kth è tra di loro. Ora per ogni mediana, sappiamo se il kth è maggiore o minore, quindi possiamo buttare via metà di ogni array. Ripetere. Una volta che gli array sono tutti un elemento lungo (o meno), usiamo l’algoritmo di selezione.

L’implementazione di questo rivelerà ulteriori complessità e condizioni marginali, ma nulla che aumenti la complessità asintotica. Ogni passo

  1. Trova le mediane o le matrici, O(1) ciascuna, quindi O(n) totale
  2. Ordina le mediane O(n log n)
  3. Cammina attraverso la lista ordinata O(n)
  4. Segue gli array O(1) ciascuno, O(n) totale

questo è O(n) + O(n log n) + O(n) + O(n) = O(n log n) . E, dobbiamo eseguirlo fino a quando l’array più lungo non è la lunghezza 1, che eseguirà i passi logm per un totale di O(n*log(n)*log(m))


Chiedi se questo può essere generalizzato al caso di matrici non ordinate. Purtroppo, la risposta è no. Considerare il caso in cui abbiamo solo un array, quindi il miglior algoritmo dovrà confrontarsi almeno una volta con ciascun elemento per un totale di O(m) . Se esistesse una soluzione più rapida per n matrici non ordinate, potremmo implementare la selezione suddividendo il nostro singolo array in n parti. Poiché abbiamo appena dimostrato che la selezione è O(m) , siamo bloccati.

Potresti guardare la mia risposta recente alla domanda correlata qui . La stessa idea può essere generalizzata a più array anziché 2. In ogni iterazione è ansible rifiutare la seconda metà dell’array con l’elemento medio più grande se k è inferiore alla sum degli indici medi di tutti gli array. In alternativa, puoi rifiutare la prima metà dell’array con l’elemento medio più piccolo se k è maggiore della sum degli indici medi di tutti gli array, regola k. Continuate a farlo fino a quando tutti gli array tranne uno si ridurranno a 0 in lunghezza. La risposta è kesimo elemento dell’ultimo array che non è stato rimosso a 0 elementi.

Analisi run-time:

Ti sbarazzi di metà di un array in ogni iterazione. Ma per determinare quale array verrà ridotto, si passa il tempo in modo lineare al numero di array. Assumendo che ogni array abbia la stessa lunghezza, il tempo di esecuzione sarà c c log (n), dove c è il numero di matrici e n è la lunghezza di ciascun array.

Se la k non è così grande, possiamo mantenere una coda minima di priorità. quindi esegui il ciclo per ogni capo dell’array ordinato per ottenere l’elemento più piccolo e la coda in coda. quando la dimensione della coda è k. otteniamo il primo k più piccolo.

forse possiamo considerare l’array n ordinato come bucket, quindi provare il metodo di ordinamento del bucket.

Questo potrebbe essere considerato la seconda metà di un ordinamento di fusione. Potremmo semplicemente unire tutte le liste ordinate in una singola lista … ma solo tenere k elementi negli elenchi combinati da unire per unire. Questo ha il vantaggio di usare solo lo spazio O (k), ma qualcosa di leggermente migliore della complessità di O (n log n) di unire merge. Cioè, dovrebbe in pratica funzionare leggermente più veloce di un ordinamento di fusione. La scelta del k più piccolo dall’elenco combinato finale è O (1). Questo tipo di complessità non è così male.

Esiste una generalizzazione che risolve il problema nel tempo O (N log k), vedere la domanda qui .

Si prega di trovare il seguente codice C # per trovare il k-esimo elemento più piccolo nell’Unione di due ordinamenti. Complessità del tempo: O (logk)

 public int findKthElement(int k, int[] array1, int start1, int end1, int[] array2, int start2, int end2) { // if (k>m+n) exception if (k == 0) { return Math.Min(array1[start1], array2[start2]); } if (start1 == end1) { return array2[k]; } if (start2 == end2) { return array1[k]; } int mid = k / 2; int sub1 = Math.Min(mid, end1 - start1); int sub2 = Math.Min(mid, end2 - start2); if (array1[start1 + sub1] < array2[start2 + sub2]) { return findKthElement(k - mid, array1, start1 + sub1, end1, array2, start2, end2); } else { return findKthElement(k - mid, array1, start1, end1, array2, start2 + sub2, end2); } }