3264. État final du tableau après k opérations de multiplication i

difficulté: facile

sujets: array, math, tas (file d'attente de priorité), simulation

vous avez un tableau entier nums, un entier k, et un multiplicateur entier.

Vous devez effectuer des k opérations sur nums. Dans chaque opération:

• Trouvez la valeur minimale x en nums. S'il y a plusieurs occurrences de la valeur minimale, sélectionnez celle qui apparaît d'abord .
• Remplacez la valeur minimale sélectionnée x par le multiplicateur x *.

return un tableau entier dénotant l'état final de nums après avoir effectué toutes les k opérations .

Exemple 1:

• entrée: nums = [2,1,3,5,6], k = 5, multiplier = 2
• sortie: [8,4,6,5,6]
• Explication:

| Opération | Résultat |
| ------------------- | ----------------- |
| Après l'opération 1 | [2, 2, 3, 5, 6] |
| Après l'opération 2 | [4, 2, 3, 5, 6] |
| Après l'opération 3 | [4, 4, 3, 5, 6] |
| Après l'opération 4 | [4, 4, 6, 5, 6] |
| Après l'opération 5 | [8, 4, 6, 5, 6] |

Exemple 2:

• entrée: nums = [1,2], k = 3, multiplicateur = 4
• output: [16,8]
• Explication:

| Opération | Résultat |
| ------------------- | ----------------- |
| Après l'opération 1 | [2, 2, 3, 5, 6] |
| Après l'opération 2 | [4, 2, 3, 5, 6] |
| Après l'opération 3 | [4, 4, 3, 5, 6] |
| Après l'opération 4 | [4, 4, 6, 5, 6] |
| Après l'opération 5 | [8, 4, 6, 5, 6] |

contraintes:

• 1
• 1
• 1
• 1

Indice:

1. maintenir les paires triées (nums [index], index) dans une file d'attente prioritaire.
2. simulez l'opération k fois.

Solution:

Nous devons implémenter les opérations comme décrit dans l'instruction Problème. Les étapes de clé consistent à trouver la valeur minimale dans le tableau, à la remplacer par la valeur multipliée par le multiplicateur donné, puis à répéter ce processus k fois.

Étant donné que nous devons sélectionner la première occurrence de la valeur minimale et la remplacer, nous pouvons aborder ceci en gardant une trace de l'index de la valeur minimale pendant chaque opération. L'implémentation PHP utilisera une file d'attente prioritaire (min-heap) pour récupérer et mettre à jour efficacement la valeur minimale pendant chaque opération.

implémentons cette solution dans php: 3264. État final du tableau après k opérations de multiplication i

Explication:

1. initialisation : Loop k fois puisque vous devez effectuer des opérations.
2. trouver une valeur minimale :
   • itérera les numéros du tableau pour trouver la plus petite valeur et son index de première occurrence .
3. Multiply la valeur minimale :
   • Remplacez la valeur à l'index identifié par le produit de la valeur actuelle et du multiplicateur.
4. Répéter:
   • Répétez les étapes ci-dessus pour k itérations.
5. renvoie le tableau final :
   • renvoie le tableau modifié après toutes les opérations.

Tester la sortie

pour les cas de test fournis:

Cas de test 1:

Saisir:

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

Sortir:

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

Cas de test 2:

Saisir:

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

Sortir:

Output: [16, 8]

Complexité

1. complexité temporelle :

   • Pour chacune des k opérations, trouver la valeur minimale dans le tableau nécessite o (n).
   • total: o (k x n) , où n est la taille du tableau.

2. Complexité spatiale :

   • La solution utilise o (1) Espace supplémentaire.

Cette solution adhère aux contraintes et fournit les résultats attendus pour tous les cas de test.

liens de contact

Si vous avez trouvé cette série utile, veuillez envisager de donner le référentiel une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• linkedIn
• github