C #: algoritmo efficiente per trovare i più grandi elementi m in una matrice N x N

Question

Vorrei sapere se esiste un algoritmo efficiente per trovare i più grandi elementi m in una matrice N x N, con un'intestazione del metodo come questa:

double[] greatestValues(double[][] matrix, int numberOfElements);

Qualche idea?

Answer 1

Se trattate la matrice N x N come una matrice di elementi N x N, potete applicare una delle seguenti tecniche:

  

Applicazione diretta dell'algoritmo di selezione basato sull'ordinamento rapido Il rapido   l'algoritmo di selezione basato sull'ordinamento può essere   usato per trovare k più piccolo o k più grande   elementi. Per trovare k elementi più piccoli   trova il kth elemento più piccolo usando   la mediana delle mediane basata sull'ordinamento rapido   algoritmo. Dopo la partizione che   trova il kth elemento più piccolo, tutto   gli elementi più piccoli del kth   sarà presente un elemento più piccolo a sinistra   all'elemento kth e tutto l'elemento   più grande sarà presente fino al   kth elemento più piccolo. Quindi tutto   elementi dal 1 ° al kth elemento   compreso costituisce il k più piccolo   elementi. La complessità temporale è   lineare in n, il numero totale di   elementi.

     

Soluzioni basate sulla struttura dei dati Un altro metodo semplice è quello di aggiungere ciascuno   elemento dell'elenco in un ordinato   imposta la struttura dei dati, come un heap o   albero di ricerca binario autobilanciante,   con al massimo k elementi. Ogni volta che il   la struttura dei dati ha più di k   elementi, rimuoviamo il più grande   elemento, che può essere fatto in O (log k)   tempo. Ogni operazione di inserimento anche   impiega tempo O (log k), risultante in   O (nlog k) tempo complessivo.

     

È possibile trasformare l'elenco   in un heap in & # 920; (n) tempo, e poi   attraversare l'heap usando un modificato   Al primo algoritmo di ricerca che   posiziona gli elementi in una priorità   Coda (anziché la coda ordinaria   che viene normalmente utilizzato in un BFS) e   termina la scansione dopo aver attraversato   esattamente k elementi. Come la dimensione della coda   rimane O (k) per tutta la traversata,   richiederebbe O (klog k) tempo a   completo, portando a un limite di tempo   O (n + klog k) su questo algoritmo.

Da qui .