Rangtransformation eines Arrays

1331. Rangtransformation eines Arrays

Schwierigkeit:Einfach

Themen:Array, Hash-Tabelle, Sortieren

Ersetzen Sie bei einem gegebenen Array von ganzen Zahlen arr jedes Element durch seinen Rang.

Der Rang gibt an, wie groß das Element ist. Für den Rang gelten folgende Regeln:

• Rang ist eine Ganzzahl beginnend bei 1.
• Je größer das Element, desto größer der Rang. Wenn zwei Elemente gleich sind, muss ihr Rang gleich sein.
• Der Rang sollte so klein wie möglich sein.

Beispiel 1:

• Eingabe: arr = [40,10,20,30]
• Ausgabe: [4,1,2,3]
• Erklärung: 40 ist das größte Element. 10 ist die kleinste. 20 ist die zweitkleinste. 30 ist die drittkleinste.

Beispiel 2:

• Eingabe: arr = [100,100,100]
• Ausgabe: [1,1,1]
• Erklärung:Gleiche Elemente haben denselben Rang.

Beispiel 3:

• Eingabe: arr = [37,12,28,9,100,56,80,5,12]
• Ausgabe: [5,3,4,2,8,6,7,1,3]

Einschränkungen:

• 0 <= arr.length <= 10⁵
• -10⁹ <= arr[i] <= 10⁹

Hinweis:

1. Verwenden Sie ein temporäres Array, um das Array zu kopieren und zu sortieren.
2. Der Rang jedes Elements ist die Anzahl der eindeutigen Elemente, die kleiner sind als es im sortierten Array plus eins.

Lösung:

Wir können es in die folgenden Schritte unterteilen:

1. Kopieren und sortieren Sie das Array: Dies hilft bei der Bestimmung des Rangs jedes einzelnen Elements.
2. Verwenden Sie eine Hash-Map, um Elementen Ränge zuzuweisen: Da mehrere Elemente denselben Wert haben können, hilft eine Hash-Map (assoziatives Array in PHP), jedes Element seinem Rang zuzuordnen.
3. Ersetzen Sie die ursprünglichen Elemente durch ihre Ränge:Mit der Hash-Map können wir jedes Element im ursprünglichen Array durch seinen entsprechenden Rang ersetzen.

Lassen Sie uns diese Lösung in PHP implementieren: 1331. Rangtransformation eines Arrays

  
  
  Erläuterung:




Kopieren und sortieren Sie das Array:


Wir erstellen eine Kopie des Eingabearrays $sorted und sortieren es. Dies hilft bei der Bestimmung des Rangs jedes einzelnen Elements.



Elementen Ränge zuweisen:


Wir durchlaufen das sortierte Array und verwenden eine Hash-Map $rank, um den Rang jedes einzelnen Elements zu speichern.
Wir verwenden isset, um zu prüfen, ob einem Element bereits ein Rang zugewiesen wurde. Wenn nicht, weisen wir den aktuellen Rang zu und erhöhen ihn.



Elemente durch ihre Ränge ersetzen:


Wir durchlaufen dann das ursprüngliche Array und ersetzen jedes Element durch seinen entsprechenden Rang, indem wir es in der $rank-Hash-Map nachschlagen.





  
  
  Zeitkomplexität:



Das Sortieren des Arrays erfordert O(n log n), wobei n die Größe des Arrays ist.
Das Zuweisen von Rängen und das Ersetzen von Werten erfordert O(n).
Die Gesamtzeitkomplexität beträgt O(n log n).


Diese Lösung verwaltet große Arrays effizient und behält gleichzeitig die Einfachheit bei.

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 vonRangtransformation eines Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!