3264. Estado da matriz final após k operações de multiplicação I

Dificuldade: Easy

tópicos: Array, Math, Heap (fila de prioridade), simulação

você recebe um número inteiro de matriz, um inteiro k e um multiplicador inteiro.

você precisa executar operações de k no NUMS. Em cada operação:

• Encontre o valor mínimo x em nums. Se houver múltiplas ocorrências do valor mínimo, selecione o que aparece primeiro .
• substitua o valor mínimo selecionado x com x * multiplicier.

retornar uma matriz inteira que denota o estado final de nums depois de executar todas as operações k .

Exemplo 1:

• entrada: nums = [2,1,3,5,6], k = 5, multiplicador = 2
• output: [8,4,6,5,6]
• Explicação:

| Operação | Resultado |
| --------------------- | ----------------- |
| Após a operação 1 | [2, 2, 3, 5, 6] |
| Após a operação 2 | [4, 2, 3, 5, 6] |
| Após a operação 3 | [4, 4, 3, 5, 6] |
| Após a operação 4 | [4, 4, 6, 5, 6] |
| Após a operação 5 | [8, 4, 6, 5, 6] |

Exemplo 2:

• input: nums = [1,2], k = 3, multiplicador = 4
• output: [16,8]
• Explicação:

| Operação | Resultado |
| --------------------- | ----------------- |
| Após a operação 1 | [2, 2, 3, 5, 6] |
| Após a operação 2 | [4, 2, 3, 5, 6] |
| Após a operação 3 | [4, 4, 3, 5, 6] |
| Após a operação 4 | [4, 4, 6, 5, 6] |
| Após a operação 5 | [8, 4, 6, 5, 6] |

restrições:

• 1
• 1
• 1
• 1

Dica:

1. Mantenha pares classificados (nums [index], index) em uma fila de prioridade.
2. simular a operação K Times.

Solução:

precisamos implementar as operações conforme descrito na instrução Problema. As etapas principais são encontrar o valor mínimo na matriz, substituí -lo pelo valor multiplicado pelo multiplicador dado e, em seguida, repita esse processo K vezes.

Dado que precisamos selecionar a primeira ocorrência do valor mínimo e substituí -lo, podemos abordá -lo, acompanhando o índice do valor mínimo durante cada operação. A implementação do PHP usará uma fila de prioridade (Min-HEAP) para recuperar e atualizar com eficiência o valor mínimo durante cada operação.

Vamos implementar esta solução em php: 3264. Estado da matriz final após k operações de multiplicação i

Explicação:

1. Inicialização : Loop K Times, pois você precisa executar o K Operations.
2. Encontre o valor mínimo :
   • iterar sobre os nums da matriz para encontrar o menor valor e seu Primeira Ocorrência Índice .
3. multiplique o valor mínimo :
   • substitua o valor no índice identificado pelo produto do valor atual e do multiplicador.
4. Repita:
   • Repita as etapas acima para k iterações.
5. retorna a matriz final :
   • retorna a matriz modificada depois de todas as operações.

Saída de teste

para os casos de teste fornecidos:

Caso de teste 1:

Entrada:

$nums = [2, 1, 3, 5, 6];
$k = 5;
$multiplier = 2;

Saída:

Output: [8, 4, 6, 5, 6]

Caso de teste 2:

Entrada:

$nums = [1, 2];
$k = 3;
$multiplier = 4;

Saída:

Output: [16, 8]

Complexidade

1. Time Complexity :

   • Para cada uma das operações k, encontrar o valor mínimo na matriz requer o (n).
   • TOTAL: o (k x n) , where n é o tamanho do array.

2. Complexidade do espaço :

   • A solução usa o (1) extra espaço.

Esta solução adere às restrições e fornece os resultados esperados para todos os casos de teste.

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