Mindestanzahl an Bällen in einer Tasche

1760. Mindestanzahl an Bällen in einer Tasche

Schwierigkeit:Mittel

Themen:Array, Binäre Suche

Sie erhalten ein ganzzahliges Array nums, wobei der i^te Beutel nums[i] Kugeln enthält. Sie erhalten außerdem eine Ganzzahl maxOperations.

Sie können den folgenden Vorgang höchstens in maxOperations-Zeiten ausführen:

• Nehmen Sie eine beliebige Tüte Bälle und teilen Sie sie in zwei neue Tüten mit einer positiven Anzahl an Bällen auf.
  • Zum Beispiel können aus einem Beutel mit 5 Bällen zwei neue Beutel mit 1 und 4 Bällen oder zwei neue Beutel mit 2 und 3 Bällen werden.

Ihre Strafe ist die maximale Anzahl an Bällen in einem Beutel. Sie möchten Ihre Strafe nach den Operationen minimieren.

Geben Sie die minimal mögliche Strafe nach Durchführung der Vorgänge zurück.

Beispiel 1:

• Eingabe: nums = [9], maxOperations = 2
• Ausgabe: 3
• Erklärung:
  • Teilen Sie den Beutel mit 9 Bällen in zwei Beutel der Größen 6 und 3. [9] -> [6,3].
  • Teilen Sie den Beutel mit 6 Bällen in zwei Beutel der Größen 3 und 3. [6,3] -> [3,3,3].
  • Der Beutel mit den meisten Bällen enthält 3 Bälle, also beträgt Ihre Strafe 3 und Sie sollten 3 zurückgeben.

Beispiel 2:

• Eingabe: nums = [2,4,8,2], maxOperations = 4
• Ausgabe: 2
• Erklärung:
  • Teilen Sie den Beutel mit 8 Bällen in zwei Beutel der Größen 4 und 4. [2,4,8,2] -> [2,4,4,4,2].
  • Teilen Sie den Beutel mit 4 Bällen in zwei Beutel der Größen 2 und 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
  • Teilen Sie den Beutel mit 4 Bällen in zwei Beutel der Größen 2 und 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
  • Teilen Sie den Beutel mit 4 Bällen in zwei Beutel der Größen 2 und 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
  • Der Beutel mit den meisten Bällen enthält 2 Bälle, daher beträgt Ihre Strafe 2, und Sie sollten 2 zurückgeben.

Einschränkungen:

• 1 5
• 1 9

Hinweis:

1. Ändern wir die Frage: Wenn wir die maximale Größe einer Tüte kennen, wie hoch ist die Mindestanzahl an Tüten, die Sie herstellen können?
2. Beachten Sie, dass mit zunehmender Maximalgröße die Mindestanzahl der Taschen abnimmt, sodass wir die Maximalgröße binär durchsuchen können

Lösung:

Wir können die binäre Suche verwenden, um die minimal mögliche Strafe zu finden. Die wichtigste Erkenntnis besteht darin, dass wir den Suchbereich mithilfe der binären Suche eingrenzen können, wenn wir feststellen können, ob eine bestimmte Strafe erreichbar ist.

Schritte zur Lösung:

1. Einrichtung der binären Suche:

   • Die Mindeststrafe beträgt 1 (alle Bälle werden in Einzelballtaschen aufgeteilt).
   • Die maximale Strafe ist die größte Zahl im Nums-Array.

2. Machbarkeitsprüfung:

   • Überprüfen Sie für eine bestimmte Strafmitte, ob es möglich ist, diese mit höchstens maxOperations-Splits zu erreichen.
   • Berechnen Sie dazu für jede Beutelgröße in Zahlen die Anzahl der Teilungen, die erforderlich sind, damit alle Beutel mittlere Kugeln oder weniger haben. Wenn die Gesamtaufteilung maxOperations überschreitet, ist die Strafe „mid“ nicht möglich.

3. Iterieren:

   • Verwenden Sie die binäre Suche, um den Bereich [niedrig, hoch] basierend darauf anzupassen, ob eine Strafe in der Mitte machbar ist.

Lassen Sie uns diese Lösung in PHP implementieren: 1760. Mindestanzahl an Bällen in einer Tasche

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

/**
 * Helper function to check if a penalty is feasible
 *
 * @param $nums
 * @param $maxOperations
 * @param $penalty
 * @return bool
 */
function canAchievePenalty($nums, $maxOperations, $penalty) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$nums = [9];
$maxOperations = 2;
echo minimumSize($nums, $maxOperations); // Output: 3

// Example 2
$nums = [2, 4, 8, 2];
$maxOperations = 4;
echo minimumSize($nums, $maxOperations); // Output: 2
?>

Erläuterung:

1. Binäre Suche:

   • Der Suchraum liegt zwischen 1 und der maximalen Zahl im Nums-Array.
   • Der Mittelpunkt stellt die aktuelle Strafe dar, die wir testen.

2. Machbarkeitsprüfung (canAchievePenalty):

   • Berechnen Sie für jeden Beutel die erforderlichen Teilungen, um sicherzustellen, dass alle Beutel mittlere Kugeln oder weniger haben:
     • ceil(balls/mid) – 1 gibt die Anzahl der benötigten Teilungen an.
   • Wenn die Gesamtzahl der Teilungen maxOperations überschreitet, ist die Strafe nicht durchführbar.

3. Suchbereich anpassen:

   • Wenn die Strafe machbar ist, reduzieren Sie die Obergrenze (hoch = mittel).
   • Wenn nicht, erhöhen Sie die Untergrenze (niedrig = Mitte 1).

4. Ergebnis:

   • Wenn die Schleife endet, enthält low die kleinste mögliche Strafe.

Komplexität:

• Zeitkomplexität: O(n . log(max(nums)))
  • Binäre Suche läuft in O(log(max(nums))) und die Machbarkeitsprüfung für jeden Mittelpunkt dauert O(n).
• Raumkomplexität: O(1), da wir nur ständig zusätzlichen Raum nutzen.

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 vonMindestanzahl an Bällen in einer Tasche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!