Ordenar pela ordem de outra lista
A missão
Problema
Uma loja ordena seus códigos de estoque por uma ordem preferida, definida pelo time de marketing. Dados values e uma lista order de códigos distintos, reorganize values para que os códigos que aparecem em order venham primeiro, agrupados e na mesma sequência de order, seguidos de todos os outros códigos em ordem crescente. As duas listas têm no máximo 1.000 itens, todo código de order também aparece em values, e cada código está entre 0 e 1.000.
Exemplos
Input: values = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], order = [2, 1, 4, 3, 9, 6]
Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
Por quê: 7 e 19 não estão em order, então vão para o fim em ordem crescente
Input: values = [28, 6, 22, 8, 44, 17], order = [22, 28, 8, 6]
Output: [22, 28, 8, 6, 17, 44]
Input: values = [5, 5], order = []
Output: [5, 5]
Por quê: edge case: com order vazia, o resultado é uma simples ordenação crescente
Dicas
0 / 3
Os códigos são inteiros pequenos, então você pode contar quantas vezes cada um aparece em vez de compará-los.
Com as contagens em mãos, a saída é só um percurso: primeiro por order, depois por todos os códigos de 0 para cima.
Para cada código em order, emita-o tantas vezes quanto ele foi contado e zere a contagem dele. Depois, varra de 0 a 1.000 e emita as contagens que sobraram.
- Tempo-alvo
- O(n + k)
- Espaço-alvo
- O(n + k)
Restrições
- values.length ≤ 1,000 and order.length ≤ 1,000
- 0 ≤ code ≤ 1,000
- codes in order are distinct
- every code in order also appears in values
Solução
Como todo código fica entre 0 e 1.000, um array de contagem substitui totalmente as comparações. Uma passada por values registra quantas cópias de cada código existem. Percorrer order, então, emite cada código preferido o número certo de vezes, e zerar a contagem dele garante que ele não seja emitido de novo. A varredura final por todos os códigos possíveis, do menor para o maior, emite as sobras em ordem crescente, que é exatamente o final que o problema pede. Com k = 1.001 códigos possíveis, o tempo é O(n + k) e o espaço extra é O(k).
def relative_sort(values, order, top=1000):
counts = [0] * (top + 1)
for v in values:
counts[v] += 1
out = []
for code in order: # preferred codes first, grouped
out += [code] * counts[code]
counts[code] = 0
for code in range(top + 1): # the rest, ascending
out += [code] * counts[code]
return out
print(relative_sort([2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19], [2, 1, 4, 3, 9, 6])) # -> [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]
print(relative_sort([28, 6, 22, 8, 44, 17], [22, 28, 8, 6])) # -> [22, 28, 8, 6, 17, 44]
print(relative_sort([5, 5], [])) # -> [5, 5]Travou na ideia, e não no código? Counting sort explica isso.