. Lexikografische Zahlen

386. Lexikografische Zahlen

Schwierigkeit:Mittel

Themen:Tiefensuche, Versuch

Bei einer gegebenen ganzen Zahl n werden alle Zahlen im Bereich [1, n] in lexikografischer Reihenfolge sortiert zurückgegeben.

Sie müssen einen Algorithmus schreiben, der in O(n) Zeit läuft und O(1) zusätzlichen Speicherplatz verwendet.

Beispiel 1:

• Eingabe: n = 13
• Ausgabe: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Beispiel 2:

• Eingabe: n = 2
• Ausgabe: 4
• Erklärung: [1,2]

Einschränkungen:

• 1 <= n <= 5 * 10⁴

Lösung:

Wir können es mit einer DFS-ähnlichen Strategie (Depth First Search) angehen.

Wichtige Erkenntnisse:

• Lexikografische Ordnung ist im Wesentlichen eine Vorordnungsdurchquerung über einen virtuellen n-fachen Baum, wobei der Wurzelknoten bei 1 beginnt und jeder Knoten bis zu 9 untergeordnete Knoten hat, die durch Anhängen von Ziffern (0 bis 9) gebildet werden.
• Wir können diesen Vorbestellungsdurchlauf simulieren, indem wir mit 1 beginnen und wiederholt Zahlen anhängen, um sicherzustellen, dass wir die angegebene n nicht überschreiten.

Ansatz:

1. Beginnen Sie mit der Zahl 1 und versuchen Sie, tiefer zu gehen, indem Sie mit 10 multiplizieren (d. h. die nächste lexikografische Zahl mit der nächsten Ziffer).
2. Wenn ein tieferes Vorgehen (Multiplizieren mit 10) nicht möglich ist (d. h. n überschreitet), erhöhen Sie die Zahl und stellen Sie sicher, dass dadurch kein ungültiger Sprung über Zehnerstellen entsteht (d. h. von 19 auf 20).
3. Wir kehren zurück, wenn die aktuelle Nummer nicht weiter verlängert werden kann, und gehen zur nächsten gültigen Nummer über.
4. Fahren Sie fort, bis alle Zahlen bis n verarbeitet sind.

Lassen Sie uns diese Lösung in PHP implementieren: 386. Lexikografische Zahlen

<?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>
  
  
  Erläuterung:
</h3>

<ul>
<li>Wir behalten eine aktuelle Zahl bei und versuchen, so tief wie möglich zu gehen, indem wir sie mit 10 multiplizieren, um die nächste lexikografische Zahl zu erhalten.</li>
<li>Wenn wir nicht multiplizieren können (weil es n überschreiten würde), erhöhen wir die Zahl. Wir behandeln Fälle, in denen die Erhöhung zu Zahlen wie 20, 30 usw. führt, indem wir nach nachgestellten Nullen suchen und die aktuelle Zahl entsprechend anpassen.</li>
<li>Die Schleife wird fortgesetzt, bis wir alle Zahlen bis n in lexikografischer Reihenfolge hinzugefügt haben.</li>
</ul>

<h3>
  
  
  Beispielhafte Vorgehensweise:
</h3>

<h4>
  
  
  Eingabe: n = 13
</h4>

<ol>
<li>Beginnen Sie bei 1.</li>
<li>Multiplizieren Sie 1 mit 10 -> 10.</li>
<li>Füge 11, 12, 13 hinzu.</li>
<li>Gehen Sie zurück zu 2 und erhöhen Sie die Zahl weiter bis 9.</li>
</ol>

<h4>
  
  
  Ausgabe:
</h4>



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

Eingabe: n = 2

1. Beginnen Sie bei 1.
2. Weiter zu 2.

Ausgabe:

[1, 2]

Zeitkomplexität:

• O(n), da jede Zahl von 1 bis n genau einmal verarbeitet wird.

Raumkomplexität:

• O(1) zusätzlicher Speicherplatz wird verwendet (ohne Berücksichtigung des für das Ergebnisarray verwendeten Speicherplatzes).

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