Come trovare il kesimo elemento minimo in una matrice

Question

Come trovare il kesimo elemento minimo in una matrice

#1 da (1 voti)
#2 da (-3 voti)

0

Sto cercando un algoritmo efficiente per trovare il kesimo elemento minimo in una matrice non ordinata di n elementi, dove 1 <= k <= n . La cosa ovvia è ordinare prima l'array, quindi selezionare l'elemento k'th, che si tradurrà in un tempo di esecuzione di O(n * log(n)) Ma immagino che possa essere fatto in un modo più efficiente, dal momento che l'ordinamento dell'array sembra fare " troppo". Ad esempio, per k = 1 l'attività è trovare il minimo dell'array, che può essere fatto in O(n) .

Qualcuno conosce un algoritmo migliore per k > = 2?

sorting

posta user1369975 24.12.2015 - 05:48

fonte

2 risposte

Leggi altre domande sui tag sorting

C'è qualche motivo tecnico per preoccuparsi della velocità di lancio? Qual è il vantaggio delle funzioni globali durante la scrittura del codice funzionale

score 1 · Answer 1

Esamina attentamente l'algoritmo Quicksort. Quindi considera di volere l'elemento k-più grande dell'array ordinato e non ti interessa di nessun altro, quindi nell'algoritmo Quicksort elimina tutto ciò che non influenzerà l'elemento k-esimo. In altre parole, non ordinare alcun sottoarray che non contenga l'elemento k-esimo.

Non è ottimale, ma migliore di un tipo completo.

Potresti anche prendere in considerazione alcune regolazioni dell'algoritmo, proprio come Quicksort di solito è sintonizzato. Ciò che è ottimale per Quicksort non è sempre ottimale per ottenere l'elemento k-esimo.

score -3 · Answer 2

-3

L'array è ordinato? Se sì allora google per "Median of Medians" o "Binarysearch" o "Interpolation-search" ci sono molto più di questi, se non è ordinato, devi prima ordinarlo.

risposta data 24.12.2015 - 19:28

fonte