3264. Estado de la matriz final después de k operaciones de multiplicación i

dificultad: easy

temas: Array, Math, Heap (priority Queue), simulación

se le dan una matriz entera, un entero k y un multiplicador entero.

Debe realizar k operaciones en números. En cada operación:

• Encuentre el valor mínimo x en nums. Si hay múltiples ocurrencias del valor mínimo, seleccione el que aparece primero .
• reemplace el valor mínimo seleccionado x con x * multiplicador.

return una matriz entera que denota el estado final de los NUMS después de realizar todas las operaciones k .

Ejemplo 1:

• Entrada: nums = [2,1,3,5,6], k = 5, multiplicador = 2
• salida: [8,4,6,5,6]
• Explicación:

| Operación | Resultado |
| ------------------- | ----------------- |
| Después de la operación 1 | [2, 2, 3, 5, 6] |
| Después de la operación 2 | [4, 2, 3, 5, 6] |
| Después de la operación 3 | [4, 4, 3, 5, 6] |
| Después de la operación 4 | [4, 4, 6, 5, 6] |
| Después de la operación 5 | [8, 4, 6, 5, 6] |

Ejemplo 2:

• Entrada: nums = [1,2], k = 3, multiplicador = 4
• output: [16,8]
• Explicación:

| Operación | Resultado |
| ------------------- | ----------------- |
| Después de la operación 1 | [2, 2, 3, 5, 6] |
| Después de la operación 2 | [4, 2, 3, 5, 6] |
| Después de la operación 3 | [4, 4, 3, 5, 6] |
| Después de la operación 4 | [4, 4, 6, 5, 6] |
| Después de la operación 5 | [8, 4, 6, 5, 6] |

restricciones:

• 1
• 1
• 1
• 1

Pista:

1. Mantener pares ordenados (nums [index], index) en una cola de prioridad.
2. Simule la operación k Times.

Solución:

necesitamos implementar las operaciones como se describe en la declaración del problema. Los pasos clave son encontrar el valor mínimo en la matriz, reemplazarlo con el valor multiplicado por el multiplicador dado y luego repetir este proceso k Times.

Dado que necesitamos seleccionar la primera aparición del valor mínimo y reemplazarlo, podemos abordar esto realizando un seguimiento del índice del valor mínimo durante cada operación. La implementación de PHP utilizará una cola de prioridad (Min-Heap) para recuperar y actualizar eficientemente el valor mínimo durante cada operación.

Implementemos esta solución en php: 3264. Estado de la matriz final después de k operaciones de multiplicación i

Explicación:

1. inicialización : bucle k times ya que necesita realizar k operaciones.
2. encontrar valor mínimo :
   • iterar sobre los números de matriz para encontrar el valor más pequeño y su Index de primera ocurrencia .
3. multiplicar valor mínimo :
   • reemplace el valor en el índice identificado con el producto del valor actual y multiplicador.
4. Repetir:
   • Repita los pasos anteriores para k iteraciones.
5. Devuelve la matriz final :
   • Devuelve la matriz modificada después de todas las operaciones.

Salida de prueba

para los casos de prueba proporcionados:

Caso de prueba 1:

Aporte:

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

Producción:

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

Caso de prueba 2:

Aporte:

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

Producción:

Output: [16, 8]

Complejidad

1. Time Complexity :

   • Para cada una de las operaciones k, encontrar el valor mínimo en la matriz requiere o (n).
   • total: o (k x n) , donde n es el tamaño de la matriz.

2. espacio complejidad :

   • la solución usa o (1) espacio adicional.

Esta solución se adhiere a las restricciones y proporciona los resultados esperados para todos los casos de prueba.

Enlaces de contacto

Si encontró esta serie útil, considere dar el repositorio una estrella en GitHub o compartir la publicación en sus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si desea un contenido más útil como este, no dude en seguirme:

• linkedin
• github