386. Lexicographical Numbers
Difficulty: Medium
Topics: Depth-First Search, Trie
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Example 2:
Constraints:
Solution:
We can approach it using a Depth-First Search (DFS)-like strategy.
Let's implement this solution in PHP: 386. Lexicographical Numbers
<?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> Explanation: </h3> <ul> <li>We maintain a current number and try to go as deep as possible by multiplying it by 10 to get the next lexicographical number.</li> <li>When we can't multiply (because it would exceed n), we increment the number. We handle cases where the increment leads to numbers like 20, 30, etc., by checking for trailing zeros and adjusting the current number accordingly.</li> <li>The loop continues until we've added all numbers up to n in lexicographical order.</li> </ul> <h3> Example Walkthrough: </h3> <h4> Input: n = 13 </h4> <ol> <li>Start at 1.</li> <li>Multiply 1 by 10 -> 10.</li> <li>Add 11, 12, 13.</li> <li>Backtrack to 2 and continue incrementing up to 9.</li> </ol> <h4> Output: </h4> <pre class="brush:php;toolbar:false">[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2]
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
The above is the detailed content of . Lexicographical Numbers. For more information, please follow other related articles on the PHP Chinese website!