Pular para o conteúdo

Ordenar pela ordem de outra lista

Fácil#counting-sort#custom-order~15 min

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

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

Travou na ideia, e não no código? Counting sort explica isso.

Python 3Ctrl+Enter executa