Problema
Un'insegnante inserisce in un programma i voti di un compito e chiude l'elenco con un numero negativo qualsiasi, che serve da segnale di stop e non è un voto. Il programma deve indicare il voto centrale nell'ordine di inserimento (i voti non sono ordinati). Con k voti, quello centrale si trova in posizione k / 2, contando da 0 e arrotondando per difetto: se i voti sono in numero pari, è il secondo dei due centrali.
Implementa middle_item(values).
Input
values: i numeri nell'ordine di inserimento. La lettura si ferma al primo numero negativo, che viene ignorato insieme a tutto ciò che lo segue. Se non c'è nessun numero negativo, tutti i valori sono voti.
Output
Restituisci il voto centrale. Se prima del segnale di stop non c'è alcun voto, restituisci -1.
Vincoli
0 ≤ lunghezza di values ≤ 1000
−1000 ≤ ogni valore ≤ 1000
Esempi
Input:
values = [88, 72, 95, 60, 81, -1]
Output atteso:
expected = 95
Input:
std::vector<long long> values = {88, 72, 95, 60, 81, -1};
Output atteso:
long long expected = 95;
Input:
long[] values = new long[] {88, 72, 95, 60, 81, -1};
Output atteso:
long expected = 95;
Spiegazione
I voti sono 88, 72, 95, 60, 81: sono 5, quindi il centrale è in posizione 2, cioè 95.
Input:
values = [10, 20, 30, 40, -5, 50]
Output atteso:
expected = 30
Input:
std::vector<long long> values = {10, 20, 30, 40, -5, 50};
Output atteso:
long long expected = 30;
Input:
long[] values = new long[] {10, 20, 30, 40, -5, 50};
Output atteso:
long expected = 30;
Spiegazione
La lettura si ferma a −5 e restano 4 voti; in posizione 2 c'è 30.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Copia i valori in una nuova lista finché non incontri il primo numero negativo.
Suggerimento 2
Con k elementi l'indice centrale è k / 2 con divisione intera.
Suggerimento 3
Se non hai copiato nulla, non c'è un elemento centrale.
Complessità attesa
tempo O(n), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.