Transformation de rang d'un tableau

1331. Transformation de rang d'un tableau

Difficulté :Facile

Sujets : Tableau, table de hachage, tri

Étant donné un tableau d'entiers arr, remplacez chaque élément par son rang.

Le rang représente la taille de l'élément. Le classement a les règles suivantes :

• Le rang est un nombre entier commençant à 1.
• Plus l'élément est grand, plus le rang est grand. Si deux éléments sont égaux, leur rang doit être le même.
• Le classement doit être aussi petit que possible.

Exemple 1 :

• Entrée : arr = [40,10,20,30]
• Sortie : [4,1,2,3]
• Explication : 40 est le plus grand élément. 10 est le plus petit. 20 est le deuxième plus petit. 30 est le troisième plus petit.

Exemple 2 :

• Entrée : arr = [100 100 100]
• Sortie : [1,1,1]
• Explication : Les mêmes éléments partagent le même rang.

Exemple 3 :

• Entrée : arr = [37,12,28,9,100,56,80,5,12]
• Sortie : [5,3,4,2,8,6,7,1,3]

Contraintes :

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

Indice :

1. Utilisez un tableau temporaire pour copier le tableau et le trier.
2. Le rang de chaque élément est le nombre d'éléments uniques inférieurs à lui dans le tableau trié plus un.

Solution :

Nous pouvons le décomposer selon les étapes suivantes :

1. Copiez et triez le tableau : Cela aide à déterminer le rang de chaque élément unique.
2. Utilisez une carte de hachage pour attribuer des rangs aux éléments : Puisque plusieurs éléments peuvent partager la même valeur, une carte de hachage (tableau associatif en PHP) aidera à mapper chaque élément à son rang.
3. Remplacez les éléments d'origine par leurs rangs : Grâce à la table de hachage, nous pouvons remplacer chaque élément du tableau d'origine par son rang correspondant.

Implémentons cette solution en PHP : 1331. Transformation de rang d'un tableau

  
  
  Explication:




Copiez et triez le tableau :


Nous créons une copie du tableau d'entrée $sorted et le trions. Cela aide à déterminer le rang de chaque élément unique.



Attribuer des rangs aux éléments :


Nous parcourons le tableau trié et utilisons une carte de hachage $rank pour stocker le classement de chaque élément unique.
Nous utilisons isset pour vérifier si un élément a déjà reçu un classement. Sinon, nous attribuons le rang actuel et l'incrémentons.



Remplacer les éléments par leurs rangs :


Nous parcourons ensuite le tableau d'origine et remplaçons chaque élément par son rang correspondant en le recherchant dans la carte de hachage $rank.





  
  
  Complexité temporelle :



Le tri du tableau prend O(n log n), où n est la taille du tableau.
Attribuer des rangs et remplacer des valeurs prend O(n).
La complexité temporelle globale est O(n log n).


Cette solution gère efficacement les grands tableaux tout en conservant la simplicité.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!