Endgültiger Array-Zustand nach K Multiplikationsoperationen I

3264. Endgültiger Array-Zustand nach K Multiplikationsoperationen I

Schwierigkeit:Einfach

Themen: Array, Mathematik, Heap (Prioritätswarteschlange), Simulation

Sie erhalten ein ganzzahliges Array „nums“, eine ganze Zahl k und einen ganzzahligen Multiplikator.

Sie müssen k Operationen für Nums ausführen. Bei jedem Vorgang:

• Finden Sie den Mindestwert x in Zahlen. Wenn der Mindestwert mehrfach vorkommt, wählen Sie den Wert aus, der zuerst erscheint.
• Ersetzen Sie den ausgewählten Mindestwert x durch x * Multiplikator.

Gibt ein ganzzahliges Array zurück, das den Endzustand von Nums angibt, nachdem alle k Operationen ausgeführt wurden.

Beispiel 1:

• Eingabe: nums = [2,1,3,5,6], k = 5, Multiplikator = 2
• Ausgabe: [8,4,6,5,6]
• Erklärung:

| Betrieb | Ergebnis |
|-------------------|-----------------|
| Nach Operation 1 | [2, 2, 3, 5, 6] |
| Nach Operation 2 | [4, 2, 3, 5, 6] |
| Nach der Operation 3 | [4, 4, 3, 5, 6] |
| Nach der Operation 4 | [4, 4, 6, 5, 6] |
| Nach der Operation 5 | [8, 4, 6, 5, 6] |

Beispiel 2:

• Eingabe: nums = [1,2], k = 3, Multiplikator = 4
• Ausgabe: [16,8]
• Erklärung:

| Betrieb | Ergebnis |
|-------------------|-----------------|
| Nach Operation 1 | [2, 2, 3, 5, 6] |
| Nach Operation 2 | [4, 2, 3, 5, 6] |
| Nach der Operation 3 | [4, 4, 3, 5, 6] |
| Nach der Operation 4 | [4, 4, 6, 5, 6] |
| Nach der Operation 5 | [8, 4, 6, 5, 6] |

Einschränkungen:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= Multiplikator <= 5

Hinweis:

1. Sortierte Paare (Nums[Index], Index) in einer Prioritätswarteschlange verwalten.
2. Simulieren Sie den Vorgang k-mal.

Lösung:

Wir müssen die Vorgänge wie in der Problemstellung beschrieben implementieren. Die wichtigsten Schritte bestehen darin, den Mindestwert im Array zu finden, ihn durch den mit dem angegebenen Multiplikator multiplizierten Wert zu ersetzen und diesen Vorgang dann k-mal zu wiederholen.

Da wir das erste Vorkommen des Mindestwerts auswählen und ersetzen müssen, können wir dies erreichen, indem wir den Index des Mindestwerts bei jedem Vorgang verfolgen. Die PHP-Implementierung verwendet eine Prioritätswarteschlange (Min-Heap), um den Mindestwert bei jedem Vorgang effizient abzurufen und zu aktualisieren.

Lassen Sie uns diese Lösung in PHP implementieren: 3264. Endgültiger Array-Zustand nach K Multiplikationsoperationen 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>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<strong>Initialisierung</strong>: Schleife k-mal, da Sie k Operationen ausführen müssen.</li>
<li>
<strong>Mindestwert finden</strong>:

<ul>
<li>Durchlaufen Sie die Array-Nummern, um den kleinsten Wert und seinen <strong>Index für das erste Vorkommen</strong> zu finden.</li>
</ul>
</li>
<li>
<strong>Mindestwert multiplizieren</strong>:

<ul>
<li>Ersetzen Sie den Wert am identifizierten Index durch das Produkt aus aktuellem Wert und Multiplikator.</li>
</ul>
</li>
<li>
<strong>Wiederholen</strong>:

<ul>
<li>Wiederholen Sie die obigen Schritte für k-Iterationen.</li>
</ul>
</li>
<li>
<strong>Das endgültige Array zurückgeben</strong>:

<ul>
<li>Gibt das geänderte Array nach allen Vorgängen zurück.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Testausgabe
</h3>

<p>Für die bereitgestellten Testfälle:</p>

<h4>
  
  
  Testfall 1:
</h4>

<p>Eingabe:<br>
</p>

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

Ausgabe:

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

Testfall 2:

Eingabe:

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

Ausgabe:

Output: [16, 8]

Komplexität

1. Zeitkomplexität:

   • Für jede der k Operationen ist O(n) erforderlich, um den Mindestwert im Array zu finden.
   • Gesamt: O(k x n), wobei n die Größe des Arrays ist.

2. Weltraumkomplexität:

   • Die Lösung verwendet O(1) zusätzlichen Speicherplatz.

Diese Lösung hält sich an die Einschränkungen und liefert die erwarteten Ergebnisse für alle Testfälle.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonEndgültiger Array-Zustand nach K Multiplikationsoperationen I. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!