Ordenar según el orden de otra lista
La misión
Problema
Una tienda ordena sus códigos de inventario según un orden preferido del equipo de marketing. Dados values y una lista order de códigos distintos, reordena values para que los códigos que aparecen en order vayan primero, agrupados y en la misma secuencia que order, seguidos de todos los demás códigos en orden ascendente. Ambas listas tienen como máximo 1000 elementos, cada código de order también aparece en values, y cada código está entre 0 y 1000.
Ejemplos
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 y 19 no están en order, así que van al final en orden ascendente
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é: caso límite: con un order vacío, el resultado es un simple ordenamiento ascendente
Pistas
0 / 3
Los códigos son enteros pequeños, así que puedes contar cuántas veces aparece cada uno en lugar de compararlos.
Con los conteos en mano, la salida es solo un recorrido: primero por order y luego por todos los códigos desde 0 hacia arriba.
Para cada código de order, agrégalo a la salida tantas veces como se contó y pon su conteo en 0. Luego recorre de 0 a 1000 y agrega lo que quede de cada conteo.
- Tiempo objetivo
- O(n + k)
- Espacio objetivo
- O(n + k)
Restricciones
- 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
Solución
Como cada código está entre 0 y 1000, un array (arreglo) de conteo reemplaza por completo las comparaciones. Una pasada sobre values registra cuántas copias hay de cada código. Luego, recorrer order agrega cada código preferido la cantidad correcta de veces, y poner su conteo en cero asegura que no se agregue otra vez. El recorrido final por todos los códigos posibles, de menor a mayor, agrega los restantes en orden ascendente, que es exactamente el tramo final que pide el problema. Con k = 1001 códigos posibles, el tiempo es O(n + k) y el espacio extra es 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]¿Lo que te frena es la idea y no el código? Counting sort lo explica.