. Numéros lexicographiques

386. Numéros lexicographiques

Difficulté :Moyen

Sujets : Recherche en profondeur d'abord, Trie

Étant donné un entier n, renvoie tous les nombres de la plage [1, n] triés par ordre lexicographique.

Vous devez écrire un algorithme qui s'exécute en temps O(n) et utilise un espace supplémentaire O(1).

Exemple 1 :

• Entrée : n = 13
• Sortie : [1,10,11,12,13,2,3,4,5,6,7,8,9]

Exemple 2 :

• Entrée : n = 2
• Sortie : 4
• Explication : [1,2]

Contraintes :

• 1 <= n <= 5*10⁴

Solution :

Nous pouvons l'aborder en utilisant une stratégie de type Depth-First Search (DFS).

Informations clés :

• L'ordre lexicographique est essentiellement un parcours de pré-ordre sur un arbre virtuel n-aire, où le nœud racine commence à 1 et chaque nœud a jusqu'à 9 enfants, qui sont formés en ajoutant des chiffres (0 à 9).
• Nous pouvons simuler ce parcours de précommande en commençant par 1 et en ajoutant des nombres à plusieurs reprises, en nous assurant de ne pas dépasser le n donné.

Approche:

1. Commencez par le chiffre 1 et essayez d'aller plus loin en multipliant par 10 (c'est-à-dire le nombre lexicographique suivant avec le chiffre suivant).
2. S'il n'est pas possible d'aller plus loin (multiplier par 10) (c'est-à-dire qu'il dépasse n), incrémentez le nombre en vous assurant qu'il n'introduit pas de saut invalide entre les dizaines (c'est-à-dire en passant de 19 à 20).
3. Nous revenons en arrière lorsque le numéro actuel ne peut pas être prolongé davantage et passons au prochain numéro valide.
4. Continuez jusqu'à ce que tous les nombres jusqu'à n soient traités.

Implémentons cette solution en PHP : 386. Numéros lexicographiques

<?php
/**
 * @param Integer $n
 * @return Integer[]
 */
function lexicalOrder($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$n1 = 13;
print_r(lexicalOrder($n1));

$n2 = 2;
print_r(lexicalOrder($n2));
?>




<h3>
  
  
  Explication:
</h3>

<ul>
<li>Nous maintenons un numéro actuel et essayons d'aller le plus loin possible en le multipliant par 10 pour obtenir le numéro lexicographique suivant.</li>
<li>Quand on ne peut pas multiplier (car il dépasserait n), on incrémente le nombre. Nous traitons les cas où l'incrément mène à des nombres comme 20, 30, etc., en vérifiant les zéros à droite et en ajustant le nombre actuel en conséquence.</li>
<li>La boucle continue jusqu'à ce que nous ayons ajouté tous les nombres jusqu'à n dans l'ordre lexicographique.</li>
</ul>

<h3>
  
  
  Exemple de procédure pas à pas :
</h3>

<h4>
  
  
  Entrée : n = 13
</h4>

<ol>
<li>Commencez à 1.</li>
<li>Multipliez 1 par 10 -> 10.</li>
<li>Ajoutez 11, 12, 13.</li>
<li>Retournez à 2 et continuez à incrémenter jusqu'à 9.</li>
</ol>

<h4>
  
  
  Sortir:
</h4>



<pre class="brush:php;toolbar:false">[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

Entrée : n = 2

1. Commencez à 1.
2. Passer à 2.

Sortir:

[1, 2]

Complexité temporelle :

• O(n) puisque chaque nombre de 1 à n est traité exactement une fois.

Complexité spatiale :

• O(1) un espace supplémentaire est utilisé (sans tenir compte de l'espace utilisé pour le tableau de résultats).

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!