Machen Sie das lexikografisch kleinste Array durch Austauschen von Elementen

2948. Machen Sie lexikographisch kleinste Array, indem Sie Elemente tauschen

Schwierigkeitsgrad: Medium

Themen: Array, Union Finden Sie, sortieren

Sie erhalten ein 0-iNDEXED Array von positiv Ganzzahlen NUMS und eine positive Ganzzahl-Grenze.

In einer Operation können Sie zwei beliebige Indizes i und j und j und nums [i] und nums [j] auswählen, wenn | nums [i] - nums [j] | & lt; = limit.

return das lexikographisch kleinste Array , das durch Ausführen der Operation eine beliebige Anzahl von Zeiten erhalten kann.

Ein Array A ist lexikographisch kleiner als ein Array B, wenn in der ersten Position, in der sich A und B unterscheiden, ein Array A ein Element hat, das weniger als das entsprechende Element in b ist. Zum Beispiel ist das Array [2,10,3] lexikographisch kleiner als das Array [10,2,3], da sie sich bei Index 0 und 2 & lt unterscheiden; 10.

Beispiel 1:

• Eingabe: nums = [1,5,3,9,8], limit = 2
• Ausgabe: [1,3,5,8,9]
• Erläuterung: Wenden Sie die Operation 2 Mal an:
  • NUMS [1] mit NUMS [2]. Das Array wird [1,3,5,9,8]
  • NUMS [3] mit NUMS [4]. Das Array wird [1,3,5,8,9]
  • Wir können ein lexikografisch kleineres Array nicht erhalten, indem wir weitere Operationen anwenden.
  • Beachten Sie, dass es möglich sein kann, dasselbe Ergebnis durch unterschiedliche Operationen zu erzielen.

Beispiel 2:

• Eingabe: nums = [1,7,6,18,2,1], limit = 3
• Ausgabe: [1,6,7,18,1,2]
• Erläuterung: Wenden Sie die Operation dreimal an:
  • NUMS [1] mit NUMS [2]. Das Array wird [1,6,7,18,2,1]
  • NUMS [0] mit NUMS [4]. Das Array wird [2,6,7,18,1,1]
  • NUMS [0] mit NUMS [5]. Das Array wird [1,6,7,18,1,2]
  • Wir können ein lexikografisch kleineres Array nicht erhalten, indem wir weitere Operationen anwenden.

Beispiel 3:

• Eingabe: nums = [1,7,28,19,10], limit = 3
• Ausgabe: [1,7,28,19,10]
• Erläuterung: [1,7,28,19,10] ist das lexikografisch kleinste Array, das wir erhalten können, da wir den Vorgang nicht auf zwei Indizes anwenden können.

Beispiel 4:

• Eingabe: nums = [1,60,34,84,62,56,39,76,49,38], Limit = 4
• Ausgabe: [1,56,34,84,60,62,38,76,49,39]

Einschränkungen:

• 1 & lt; = nums.length & lt; = 10 ⁵
• 1 & lt; = nums [i] & lt; = 10 ⁹
• 1 & lt; = limit & lt; = 10 ⁹

Hinweis:

1. Konstruieren Sie ein virtuelles Diagramm, in dem alle Elemente in NUMs Knoten sind und die Paare den Zustand erfüllen.
Anstatt alle Kanten zu konstruieren, kümmern wir uns nur um die verbundenen Komponenten.
Können wir DSU verwenden?
sortieren nums. Jetzt müssen wir nur überlegen, ob die aufeinanderfolgenden Elemente einen Vorteil haben, um zu überprüfen, ob sie derselben verbundenen Komponente angehören. Daher werden alle verbundenen Komponenten nach der Sortierung zu einer Liste von Positionskonsum-Elementen.
Für jeden Index von NUMs von 0 bis num.länge - 1 können wir ihn in den aktuellen Mindestwert ändern, den wir in seiner angeschlossenen Komponente haben und diesen Wert aus der angeschlossenen Komponente entfernen.

Lösung:

Das Problem fordert uns auf, die

lexikographisch kleinste Array zu finden, indem Elemente eines Arrays ausgetauscht werden. Insbesondere können wir nur zwei Elemente nums [i] und nums [j] tauschen, wenn der absolute Unterschied zwischen ihnen (| nums [i] - nums [j] |) kleiner als oder gleich einer gegebenen Grenze ist.

Schlüsselpunkte

1. lexikografische Ordnung : Ein Array A ist lexikographisch kleiner als B, wenn beim ersten unterschiedlichen Index A [i] & lt; B [i].
2. Tauschbedingung : Swaps sind nur zulässig, wenn die Differenz zwischen den ausgetauschten Zahlen ≤ Grenze ist.
3. effiziente Gruppierung : Durch Verwendung disjoint Set Union (DSU) oder Sortiertechniken können wir Elemente gruppieren, die durch gültige Swaps verbunden sind.
4. optimale Anordnung : Sortieren Sie für jede Gruppe die Indizes und Werte, um die kleinste Reihenfolge zu erreichen.

Ansatz

1. Konstruktgruppen : Behandeln Sie das Array als virtuelles Diagramm, wobei gültige Swaps die Kanten definieren. Verwenden Sie die Sortierung, um verbundene Gruppen oder DSU zu identifizieren, um die Gruppenindizes effizient zu gruppieren.
2. sortieren Gruppen : Innerhalb jeder Gruppe von verbundenen Indizes ordnen Sie die Elemente in lexikografischer Reihenfolge neu an.
3. Ausgabekonstruktion : Platzieren Sie die sortierten Werte wieder in ihre jeweiligen Positionen.

Plan

extrahieren (Wert, Index) Paare und sortieren Sie sie nach Wert, um eine effiziente Gruppenerkennung zu ermöglichen.
durch sortierte Werte iterieren, um Gruppen von Indizes zu bilden, die basierend auf dem Grenzzustand verbunden sind.
für jede Gruppe:
3. sortieren Indizes und Werte unabhängig.
   Werte in ihren ursprünglichen Positionen in lexikografischer Reihenfolge zuzuweisen.
Zurück das modifizierte Array.

implementieren wir diese Lösung in PHP:

2948. Machen Sie lexikographisch kleinstes Array, indem Sie Elemente tauschen

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

/**
 * @param $nums
 * @return array
 */
function getNumAndIndexes($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1, 5, 3, 9, 8];
$limit1 = 2;
print_r(lexicographicallySmallestArray($nums1, $limit1)); // Output: [1, 3, 5, 8, 9]

$nums2 = [1, 7, 6, 18, 2, 1];
$limit2 = 3;
print_r(lexicographicallySmallestArray($nums2, $limit2)); // Output: [1, 6, 7, 18, 1, 2]

$nums3 = [1, 7, 28, 19, 10];
$limit3 = 3;
print_r(lexicographicallySmallestArray($nums3, $limit3)); // Output: [1, 7, 28, 19, 10]

$nums4 = [1, 60, 34, 84, 62, 56, 39, 76, 49, 38];
$limit4 = 4;
print_r(lexicographicallySmallestArray($nums4, $limit4)); // Output: [1, 56, 34, 84, 60, 62, 38, 76, 49, 39]
?>

Erläuterung:

1. extrahieren und sortieren (getNumandIndexes):

   • Kombinieren Sie Werte und Indizes zu Paaren, um die Referenz zu erleichtern.
   • Sortieren Sie die Paare nach Wert, um eine effiziente Gruppierung verbundener Komponenten zu ermöglichen.

2. Gruppierungslogik:

   • Durchlaufen Sie die sortierten Paare. Wenn die Differenz zwischen aufeinanderfolgenden Werten ≤ limit ist, fügen Sie sie derselben Gruppe hinzu. andernfalls starten Sie eine neue Gruppe.

3. Sortieren und Neuzuordnen:

   • Für jede Gruppe:
     • Extrahieren Sie die Indizes und Werte.
     • Sortieren Sie beide Listen, um sicherzustellen, dass die kleinsten Werte in den kleinsten Indizes platziert werden.
     • Ordnen Sie die sortierten Werte ihren jeweiligen Positionen im Antwortarray neu zu.

4. Ergebniskonstruktion:

   • Nach der Verarbeitung aller Gruppen das aktualisierte Array zurückgeben.

Beispiel-Anleitung

Beispiel 1

Eingabe: nums = [1,5,3,9,8], limit = 2

1. Extrahieren und Sortieren:

   • Paare: [(1, 0), (5, 1), (3, 2), (9, 3), (8, 4)]
   • Sortierte Paare: [(1, 0), (3, 2), (5, 1), (8, 4), (9, 3)]

2. Gruppierung:

   • Gruppe 1: [(1, 0)]
   • Gruppe 2: [(3, 2), (5, 1)]
   • Gruppe 3: [(8, 4), (9, 3)]

3. Gruppen sortieren:

   • Gruppe 1: Keine Änderung ([1])
   • Gruppe 2: Werte = [3, 5], Indizes = [1, 2] → Ergebnis: [1, 3, 5]
   • Gruppe 3: Werte = [8, 9], Indizes = [3, 4] → Ergebnis: [8, 9]

4. Endergebnis: [1, 3, 5, 8, 9]

Zeitkomplexität

1. Sortieren: Das Sortieren des Nums-Arrays dauert O(n log n).
2. Gruppierung: Die lineare Durchquerung des sortierten Arrays erfordert O(n).
3. Gruppen sortieren: Das Sortieren von Indizes und Werten für jede Gruppe dauert O(k log k), wobei k ist die Gruppengröße. Über alle Gruppen summiert ergibt dies O(n log n).

Gesamtzeitkomplexität: O(n log n)

Ausgabe für Beispiele

Beispiel 2

Eingabe: nums = [1,7,6,18,2,1], limit = 3

Ausgabe: [1,6,7,18,1,2]

Beispiel 3

Eingabe: nums = [1,7,28,19,10], limit = 3

Ausgabe: [1,7,28,19,10]

Dieser Ansatz löst das Problem effizient, indem er mithilfe der Sortierung verbundene Komponenten identifiziert und Werte innerhalb jeder Komponente neu anordnet, um das lexikografisch kleinste Array zu erhalten. Durch die Nutzung von Sortierung und Gruppenverarbeitung stellen wir eine optimale Lösung mit O(n log n) Komplexität sicher.

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 vonMachen Sie das lexikografisch kleinste Array durch Austauschen von Elementen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!