Os K valores mais próximos do alvo
A missão
Problema
Dada uma lista não ordenada de inteiros nums, um target e uma quantidade k, retorne os k valores mais próximos do alvo. Quando dois valores estão à mesma distância, o menor valor conta como mais próximo. Retorne os valores escolhidos em ordem crescente.
Exemplos
Input: nums = [9, 2, 14, 5, 7, 11], target = 8, k = 3
Output: [5, 7, 9]
Por quê: 7 e 9 estão a 1 de distância; depois 5 e 11 empatam em 3 e o menor valor vence
Input: nums = [1, 10, 4, 4], target = 4, k = 2
Output: [4, 4]
Por quê: valores repetidos contam separadamente
Input: nums = [3], target = 100, k = 1
Output: [3]
Por quê: edge case: o único valor é o mais próximo, por mais longe que esteja
Dicas
0 / 3
Ordenar por distância funciona em n log n. Você só precisa de k valores, então pense no que guardaria lendo a lista uma única vez.
Guarde os k valores mais próximos vistos até agora, com o mais distante deles fácil de alcançar. Um valor novo só importa se estiver mais perto do que esse mais distante.
Guarde cada valor como (distância negada, valor negado) em um min-heap de tamanho k, para que o valor guardado mais distante, e o maior em caso de empate, fique na raiz. Substitua a raiz sempre que uma entrada nova for maior que ela na comparação e, depois, ordene os sobreviventes.
- Tempo-alvo
- O(n log k)
- Espaço-alvo
- O(k)
Solução
Este é o problema dos k pontos mais próximos em uma reta: a distância é uma única diferença absoluta, e o heap de tamanho k guarda os k melhores candidatos com o pior na raiz, pronto para ser descartado. Negar tanto a distância quanto o valor transforma o min-heap do Python nesse max-heap e embute a regra de empate na comparação, já que, em caso de empate, o valor maior é o candidato pior. Um valor novo só substitui a raiz quando a sua entrada é maior, ou seja, quando ele está mais perto, ou igualmente perto e é menor. O tempo é O(n log k) e o heap usa espaço O(k), o que importa quando a lista é um stream longo e k é pequeno.
import heapq
def closest_k(nums, target, k):
heap = [] # k closest so far, the worst at the root
for x in nums:
entry = (-abs(x - target), -x) # farther, then larger, is worse
if len(heap) < k:
heapq.heappush(heap, entry)
elif entry > heap[0]: # closer than the worst kept value
heapq.heapreplace(heap, entry)
return sorted(-x for _, x in heap)
print(closest_k([9, 2, 14, 5, 7, 11], 8, 3)) # -> [5, 7, 9]
print(closest_k([1, 10, 4, 4], 4, 2)) # -> [4, 4]
print(closest_k([3], 100, 1)) # -> [3]Travou na ideia, e não no código? Os k pontos mais próximos explica isso.