Median of Two Sorted Arrays
Você recebe duas listas de inteiros, nums1 e nums2, cada uma ordenada do menor para o maior e contendo pelo menos um valor. Retorne a mediana de todos os valores juntos, como texto.
Para uma quantidade total ímpar, a mediana é o valor do meio, como "4". Para uma quantidade par, é a média dos dois valores do meio, como "2.5" ou "-0.5". Escreva um número inteiro sem ponto decimal e zero como "0", nunca como "-0". Busque um tempo de execução de O(log(min(m, n))).
Função
- nums1integer-array
- primeira lista, ordenada do menor para o maior
- nums2integer-array
- a segunda lista, ordenada do menor para o maior
- Retornastring
- a mediana de todos os valores, como texto, por exemplo "4" ou "-2.5"
Restrições
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Ambas as listas estão ordenadas em ordem não decrescente, e os valores podem se repetir.
Exemplos
- Entrada
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Saída
- "4"
- Explicação
- Juntos, os valores são 1, 2, 4, 7, 9. Cinco valores têm um valor central, o terceiro, que é 4.
- Entrada
- nums1 = [1, 2]nums2 = [3, 4]
- Saída
- "2.5"
- Explicação
- Juntos, os valores são 1, 2, 3, 4. Os dois valores do meio são 2 e 3, a soma deles é 5, e a metade de 5 é 2,5.
- Entrada
- nums1 = [-7, -3]nums2 = [-2, 0]
- Saída
- "-2.5"
- Explicação
- Juntos, os valores são -7, -3, -2, 0. Os valores centrais -3 e -2 somam -5, e a metade de -5 é -2.5.
Para ir além
Você consegue usar o mesmo corte para encontrar o k-ésimo menor valor das duas listas, para qualquer k, em tempo logarítmico?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Mesclar as duas listas encontra a mediana em
O(m + n). Para fazer melhor, pense na mediana como um corte: uma linha que divide todos osm + nvalores em uma metade inferior e uma metade superior do mesmo tamanho.A metade inferior é um prefixo de
nums1mais um prefixo denums2. Se ela pegarivalores denums1, a quantidade denums2segue essa regra. O corte está correto quando o último valor pego de cada lista não é maior que o primeiro valor restante na outra.Faça uma busca binária de
ina lista mais curta. Se o último valor selecionado denums1for grande demais, selecione menos elementos dela; se o último valor selecionado denums2for grande demais, selecione mais. No corte correto, a mediana vem do maior valor abaixo do corte e do menor acima dele. Some esses dois inteiros e divida a soma por dois você mesmo.
Solução
Mesclar as listas fornece a mediana em O(m + n), mas a maioria dos valores lidos não pode alterar a resposta. A mediana depende apenas de onde fica o corte entre a metade inferior e a metade superior, e um número determina esse corte: quantos valores a metade inferior obtém da lista mais curta. A busca binária encontra esse valor em O(log(min(m, n))) etapas.
Mescle as duas listas
Intuição
Mescle as listas como o merge sort faz, formando uma única lista ordenada merged. Com total = m + n, some merged[(total-1)/2] e merged[total/2], usando divisão inteira. Para um total ímpar, ambos são o valor do meio; para um total par, são os dois valores do meio, então metade da soma é a mediana em ambos os casos.
Mesmo que você pare no meio, as etapas da intercalação percorrem mais da metade dos valores, então o tempo é O(m + n).
Algoritmo
- Mescle as listas em
merged, sempre pegando o menor valor atual e, depois, o restante da lista que sobrar. - Com
total = m + n, somemerged[(total-1)/2]emerged[total/2]. - Retorne metade da soma como texto: divida uma soma par por 2; para uma soma ímpar, escreva o sinal, metade do valor absoluto e
.5.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])Busca binária no corte
Intuição
Considere que a metade inferior contenha half = (m+n+1)/2 valores, incluindo o valor extra quando o total for ímpar. Ela recebe i valores do início de nums1 e j = half-i do início de nums2. O corte está correto quando nada abaixo dele é maior do que qualquer coisa acima. Cada lista está ordenada, então restam duas verificações: left1 ≤ right2 e left2 ≤ right1, em que left é o último valor que uma lista fornece à metade inferior e right é o primeiro valor que ela mantém. Um lado ausente conta como menos ou mais infinito.
Se left1 > right2, i é grande demais; se left2 > right1, é pequeno demais. Portanto, i é uma busca binária de 0 a m. Em [1, 2] e [3, 4], i = 1 falha porque left2 = 3 > right1 = 2, e i = 2 funciona: (2 + 3) / 2 = 2.5.
Algoritmo
- Faça de
nums1a lista mais curta; definahalf = (m+n+1)/2. - Faça uma busca binária por
idelo = 0atéhi = m, comj = half-i. - Leia
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]eright2 = nums2[j], considerando infinito após o fim de uma lista. - Se
left1 > right2, definahi = i-1. Seleft2 > right1, definalo = i+1. - Caso contrário, para um total ímpar, retorne
max(left1, left2). Para um total par, dividamax(left1, left2) + min(right1, right2)por dois.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
Armadilhas e casos extremos
- Divisão pela metade usando ponto flutuante. Python imprime uma mediana inteira como
3.0, e%fdo C imprime 2.5 como2.500000. Mantenha a soma como inteiro. - Escrever o quociente inteiro e
.5para uma soma ímpar negativa.-1 / 2é 0 em C e Java, resultando em 0.5 para -0.5;-5 // 2é -3 em Python, resultando em -3.5 para -2.5. Divida o valor absoluto pela metade e recoloque o sinal. - Escrever
-0. Os valores centrais -1 e 1 somam 0, e a resposta é"0". Use o sinal da soma. - Pesquisar a lista mais longa.
j = half-ipode ficar abaixo de 0 ou passar den. Troque as listas primeiro. - Ler
nums1[i-1]quandoi = 0, como em[9]e[1, 2]. Use infinitos para valores ausentes.
Perguntas frequentes3
Qual é a complexidade de tempo de Median of Two Sorted Arrays?
A busca binária no corte leva O(log(min(m, n))) de tempo e O(1) de espaço, porque cada etapa reduz pela metade os cortes possíveis na lista mais curta. A intercalação leva O(m + n): para duas listas de 3000 elementos, são cerca de 12 etapas, em comparação com 6000.
Por que fazer busca binária no array mais curto?
Como j = half-i. Como i está na lista mais curta, j permanece entre 0 e o comprimento da lista mais longa, então toda leitura está dentro do intervalo ou além de um limite que você trata como infinito.
Como retornar a mediana sem usar ponto flutuante?
Some translated text
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def findMedianSortedArrays(nums1, nums2):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
nums1 = [1, 4] nums2 = [2, 7, 9]
Saída Esperada
"4"