Problème
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.
Contraintes
0 ≤ lengths ≤ 100,000; the combined length is at least 1
Exemples
Entrée :
first = [1, 3]
second = [2]
Sortie attendue :
expected = 2.0Entrée :
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};
Sortie attendue :
double expected = 2.0;Entrée :
long[] first = new long[] {1, 3};
long[] second = new long[] {2};
Sortie attendue :
double expected = 2.0;Explication
Combined: [1, 2, 3]; the middle value is 2.
Entrée :
first = [1, 2]
second = [3, 4]
Sortie attendue :
expected = 2.5Entrée :
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Sortie attendue :
double expected = 2.5;Entrée :
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Sortie attendue :
double expected = 2.5;Explication
Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
L’ordre combiné compte, mais tu n’as pas besoin de tout fusionner si tu peux trouver directement la coupure centrale.
Indice 2
Cherche une partition où les moitiés gauche contiennent exactement les éléments du bas milieu et où chaque valeur à gauche est ≤ à chaque valeur à droite.
Indice 3
Gère soigneusement les tableaux vides et les longueurs totales impaires ou paires, car la médiane peut venir d’une seule valeur centrale ou de deux.
Complexité attendue
temps O(log(min(m, n))), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.