État final du tableau après K opérations de multiplication I

3264. État final du tableau après K opérations de multiplication I

Difficulté :Facile

Sujets : Tableau, mathématiques, tas (file d'attente prioritaire), simulation

Vous recevez un tableau entier nums, un entier k et un multiplicateur entier.

Vous devez effectuer k opérations sur les nombres. Dans chaque opération :

• Trouvez la valeur minimale x en chiffres. S'il existe plusieurs occurrences de la valeur minimale, sélectionnez celle qui apparaît en premier.
• Remplacez la valeur minimale sélectionnée x par le multiplicateur x *.

Renvoyer un tableau d'entiers indiquant l'état final des nombres après avoir effectué toutes les k opérations.

Exemple 1 :

• Entrée : nums = [2,1,3,5,6], k = 5, multiplicateur = 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
• Sortie : [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 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplicateur <= 5

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 mettre en œuvre les opérations telles que décrites dans l'énoncé du problème. Les étapes clés 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 cela en gardant une trace de l'index de la valeur minimale lors de 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 lors de chaque opération.

Implémentons cette solution en PHP : 3264. État final du tableau après K opérations de multiplication I

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @param Integer $multiplier
 * @return Integer[]
 */
function finalArrayState($nums, $k, $multiplier) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test Case 1
$nums1 = [2, 1, 3, 5, 6];
$k1 = 5;
$multiplier1 = 2;
$result1 = finalArrayState($nums1, $k1, $multiplier1);
echo "Output: [" . implode(", ", $result1) . "]\n";

// Test Case 2
$nums2 = [1, 2];
$k2 = 3;
$multiplier2 = 4;
$result2 = finalArrayState($nums2, $k2, $multiplier2);
echo "Output: [" . implode(", ", $result2) . "]\n";
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<strong>Initialisation</strong> : bouclez k fois puisque vous devez effectuer k opérations.</li>
<li>
<strong>Trouver la valeur minimale</strong> :

<ul>
<li>Parcourez les numéros du tableau pour trouver la plus petite valeur et son <strong>index de première occurrence</strong>.</li>
</ul>
</li>
<li>
<strong>Multiplier la valeur minimale</strong> :

<ul>
<li>Remplacez la valeur à l'index identifié par le produit de la valeur actuelle et du multiplicateur.</li>
</ul>
</li>
<li>
<strong>Répéter</strong> :

<ul>
<li>Répétez les étapes ci-dessus pour k itérations.</li>
</ul>
</li>
<li>
<strong>Renvoyer le tableau final</strong> :

<ul>
<li>Renvoyer le tableau modifié après toutes les opérations.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Sortie de test
</h3>

<p>Pour les cas de test fournis :</p>

<h4>
  
  
  Cas de test 1 :
</h4>

<p>Entrée :<br>
</p>

<pre class="brush:php;toolbar:false">$nums = [2, 1, 3, 5, 6];
$k = 5;
$multiplier = 2;

Sortie :

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

Cas de test 2 :

Entrée :

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

Sortie :

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 respecte les contraintes et fournit les résultats attendus pour tous les cas de tests.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

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

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!