Problema
Ordina i valori in ordine crescente. Se il numero di valori è dispari, prendi quello centrale. Se è pari, calcola la media aritmetica dei due valori centrali. Questa sfida accetta solo liste non vuote.
Implementa median_number(numbers).
Input
numbers: La lista non vuota di valori.
Output
Restituisci la mediana come numero; può terminare con .5.
Vincoli
1 ≤ lunghezza della lista ≤ 100.000. Ogni valore è un intero compreso tra −1.000.000.000 e 1.000.000.000.
Esempi
Input:
numbers = [2, 8, 4, 10]
Output atteso:
expected = 6.0Input:
std::vector<long long> numbers = {2, 8, 4, 10};
Output atteso:
double expected = 6.0;Input:
long[] numbers = new long[] {2, 8, 4, 10};
Output atteso:
double expected = 6.0;Spiegazione
L'ordine crescente è 2, 4, 8, 10. La coppia centrale ha media (4 + 8) / 2 = 6.
Input:
numbers = [9, 1, 4]
Output atteso:
expected = 4.0Input:
std::vector<long long> numbers = {9, 1, 4};
Output atteso:
double expected = 4.0;Input:
long[] numbers = new long[] {9, 1, 4};
Output atteso:
double expected = 4.0;Spiegazione
L'ordine crescente è 1, 4, 9, il cui valore centrale è 4.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
La mediana dipende dall’ordine dopo il sorting, quindi contano le posizioni nella lista ordinata.
Suggerimento 2
Dopo il sorting, usa l’elemento centrale per lunghezza dispari, oppure combina i due centrali per lunghezza pari.
Suggerimento 3
Fai attenzione a mantenere le metà quando fai la media di due valori centrali, perché il risultato può finire in .5.
Complessità attesa
tempo O(n log n), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.