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:

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.

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]
?>

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!