632. Menor alcance de abordagem de elementos de K listas

dificuldade: hard

tópicos: Array, tabela de hash, janela gananciosa, deslizante, classificação, heap (fila de prioridade)

Você tem l listas de números inteiros classificados em Ordem não decrescente . Encontre o intervalo menor que inclui pelo menos um número de cada uma das l listas.

definimos o intervalo [a, b] é menor que o intervalo [c, d] se b - a ou a

Exemplo 1:

• entrada: nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]
• output: [20,24]
• Explicação:
  • Lista 1: [4, 10, 15, 24,26], 24 está no intervalo [20,24].
  • Lista 2: [0, 9, 12, 20], 20 está no intervalo [20,24].
  • Lista 3: [5, 18, 22, 30], 22 está no intervalo [20,24].

Exemplo 2:

• entrada: nums = [[1,2,3], [1,2,3], [1,2,3]]
• output: [1,1]

restrições:

• nums.Length == K
• 1
• 1 ...
• NUMS [i] é classificado em ^{não decrescente} order.
• Solução:
podemos usar um

min-heap

(ou fila de prioridade) para rastrear o menor elemento de cada lista, mantendo uma janela deslizante para encontrar o menor intervalo que inclui pelo menos um elemento de cada lista. Abordagem

inicialização Min-Heap

: use um min-heap para armazenar os elementos atuais de cada uma das listas K. Cada entrada de heap será uma tupla contendo o valor, o índice da lista de onde vem e o índice do elemento nessa lista.

Valor máximo Rastreamento
1. : Acompanhe o valor máximo na janela atual. Isso é importante porque o intervalo é determinado pela diferença entre o menor elemento (do heap) e o máximo atual.
iterar até o final das listas
2. : para cada iteração: extraia o elemento mínimo do heap.
3. Atualize o intervalo se o intervalo atual [min_value, max_value] for menor que o menor intervalo registrado anteriormente. mova para o próximo elemento na lista da qual o elemento mínimo foi obtido. Atualize o valor máximo e adicione o novo elemento ao heap.
   terminação
   • : o processo termina quando qualquer lista é esgotada.
Vamos implementar esta solução em php:
4. 632. Menor alcance de abordagem de elementos de K listas

Php /** * @param inteiro [] [] $ nums * @return integer [] */ função smallestrange ($ nums) { ... ... ... /** * vá para ./solution.php */ } // Exemplo de uso: $ nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]; $ resultado = smallestrange ($ nums); print_r ($ resultado); // Saída: [20, 24] ?>

Explicação:

:

O heap inicial contém o primeiro elemento de cada lista. Também acompanhamos o elemento máximo entre os primeiros elementos.

1. Processando o HEAP
   • :
   extrai o elemento mínimo da pilha e, em seguida, tente estender o intervalo adicionando o próximo elemento da mesma lista (se disponível).
2. Depois de adicionar um novo elemento à pilha, atualize o maxValue se o novo elemento for maior. Atualize o menor intervalo sempre que a diferença entre o maxValue e o minvalue é menor que a faixa gravada anteriormente.
   terminação
   • :
   O loop para quando qualquer lista fica sem elementos, pois não podemos mais incluir todas as listas no intervalo.
3. Análise de complexidade
complexidade do tempo

: o (n * log k), onde n é o número total de elementos em todas as listas e k é o número de listas. A complexidade vem da inserção e remoção de elementos do heap.

complexidade do espaço
• : o (k) para armazenar elementos no heap.
Esta solução encontra com eficiência o menor intervalo que inclui pelo menos um número de cada uma das listas classificadas.
• Contato Links

Se você achou essa série útil, considere dar o

repositório

uma estrela no github ou compartilhar a postagem em suas redes sociais favoritas?. Seu apoio significaria muito para mim! Se você quiser um conteúdo mais útil como este, fique à vontade para me seguir:

Linkedin

github