Problema
Both lists are sorted in ascending order. Find the median of all their numbers together; for an even count it is the average of the two middle values. An O(log(m + n)) partition search is possible, but any correct method within the limits is accepted.
Implement median_of_two(first, second).
Input
first: A sorted list. second: A sorted list.
Output
Return the median.
Vincoli
0 ≤ lengths ≤ 100,000; the combined length is at least 1
Esempi
Input:
first = [1, 3]
second = [2]
Output atteso:
expected = 2.0Input:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};
Output atteso:
double expected = 2.0;Input:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};
Output atteso:
double expected = 2.0;Spiegazione
Combined: [1, 2, 3]; the middle value is 2.
Input:
first = [1, 2]
second = [3, 4]
Output atteso:
expected = 2.5Input:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Output atteso:
double expected = 2.5;Input:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Output atteso:
double expected = 2.5;Spiegazione
Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
L'ordine complessivo conta, ma non devi fondere tutto se riesci a trovare direttamente la divisione centrale.
Suggerimento 2
Cerca una partizione in cui le metà sinistre contengano esattamente gli elementi inferiori centrali e ogni valore a sinistra non sia maggiore di quelli a destra.
Suggerimento 3
Gestisci con attenzione gli array vuoti e le lunghezze totali dispari o pari, perché la mediana può venire da un solo valore centrale o da due.
Complessità attesa
tempo O(log(min(m, n))), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.