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.
Restrições
0 ≤ lengths ≤ 100,000; the combined length is at least 1
Exemplos
Entrada:
first = [1, 3]
second = [2]
Saída esperada:
expected = 2.0Entrada:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};
Saída esperada:
double expected = 2.0;Entrada:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};
Saída esperada:
double expected = 2.0;Explicação
Combined: [1, 2, 3]; the middle value is 2.
Entrada:
first = [1, 2]
second = [3, 4]
Saída esperada:
expected = 2.5Entrada:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Saída esperada:
double expected = 2.5;Entrada:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Saída esperada:
double expected = 2.5;Explicação
Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A ordem combinada importa, mas você não precisa mesclar tudo se conseguir encontrar direto a divisão do meio.
Dica 2
Procure uma partição em que as metades esquerdas contenham exatamente os elementos menores do meio e todo valor à esquerda não seja maior que qualquer valor à direita.
Dica 3
Trate com cuidado arrays vazios e os casos com total ímpar ou par, já que a mediana pode vir de um valor central ou de dois.
Complexidade esperada
tempo O(log(min(m, n))), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.