Dato N numeri interi arbitrari, come trovare la media della metà superiore di questi numeri? Esiste una soluzione O (n)? Se no è possibile provare che non è possibile?Come trovare la media della metà superiore di N numeri?
Innanzitutto, trovare uno median dell'array dato (è takes linear time).
Quindi, basta camminare attraverso la matrice e riassumere tutti gli elementi che sono maggiori della mediana.
Contare quanti elementi sono stati sommati (M). Se M < N/2, significa che diversi elementi uguali al valore mediano (ovvero, N/2 - M) appartengono alla metà superiore. Aggiungi alla tua somma tanti valori mediani. Abbiamo bisogno di questa complessità perché non sappiamo quanti elementi mediani (ce ne possono essere diversi) appartengono alla metà superiore: se li prendiamo tutti, possiamo concludere che abbiamo sommato più di N/2 elementi.
Ora si ha la somma della metà superiore dell'array. Dividi per N/2 e il gioco è fatto.
Oppure il codice potrebbe essere più semplice se si esegue un passaggio O (n) extra e si conta solo il numero di elementi uguale alla mediana. Questo ti dice quanti elementi uguali alla mediana includere nella media. –
Ancora più semplice sarebbe utilizzare quasi tutti gli algoritmi per trovare una mediana e trovare una partizione dell'elenco di input in una parte superiore e inferiore. Quindi una volta trovata la mediana tutti gli elementi nella metà superiore sono già noti. – Accipitridae
vorrei suggerire questo:
Usa Quicksort, selezionare alcune pivot. Questa partizione verrà suddivisa in due sottoliste, una più piccola del pivot, una più grande di quella. Se la dimensione della sottolista più piccola è < = N/2, calcolare la media dire a1.
Se size == N/2 or size == N/2 -1
hai finito immediatamente.
Se non la ripartizione, la sottolista maggiore fino alla dimensione totale è N/2.
Se la dimensione> N/2 divide la sottolista più piccola.
Ripeti tutto fino a fine.
P.S: non è necessario ordinare.
È 'O (n^2)' nel peggiore dei casi ... –
È possibile utilizzare una coda di priorità. Inserisci gli elementi nella coda mantenendo un conteggio del numero di elementi che hai visto, n. Estrai n/2 elementi massimi dalla coda in un accumulatore e calcola la media.
Con una struttura dati ben selezionata dietro la coda, ad esempio un heap di Fibonacci, si otterrà il runtime O(n log n), poiché l'inserimento è O(1) e l'estrazione è O(log n).
Sfortunatamente non il tempo di esecuzione O (n) che stavi cercando, ma con la struttura dati già implementata, questo produrrebbe un codice diretto molto comprensibile.
* Trovare * il massimo è O (1) in un heap di Fibonacci, ma * rimuoverlo * (consentendo così a quale era il secondo-massimo essere trovato in un altro O (1)) è O (log n). Se "insert" e "remove max" erano veramente entrambi O (1) in un heap di Fibonacci, allora sarebbe possibile usarne uno per eseguire un ordinamento di confronto in O (n). –
Hai perfettamente ragione, mi scuso, ho modificato la mia risposta di conseguenza. Quel fastidioso nlogn inferiore legato allo smistamento! –
Questo è ovviamente risolvibile in tempo lineare, se è possibile trovare la mediana in tempo lineare. E trovare una mediana in tempo lineare è complicato, ma possibile. Vedi ad esempio l'articolo di Wikipedia su selection algorithms.
La domanda dovrebbe riguardare la programmazione (ad esempio, risolvere questo utilizzando un programma)? – BoltClock
Io donno. Puoi dare una formula matematica se hai un metodo. È solo una domanda per un colloquio. – Seeker
Questa è una delle domande, in cui l'intervistatore vuole sapere se il candidato può ridurre i problemi del mondo reale agli algoritmi noti. Questo è spesso più importante della possibilità di recitare gli algoritmi stessi. Quindi, ho difficoltà a capire perché questa domanda è stata chiusa come fuori tema. – Accipitridae