. Lexicographical Numbers

Mary-Kate Olsen
发布: 2024-09-21 12:16:09
原创
508 人浏览过

. Lexicographical Numbers

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:

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

Example 2:

  • Input: n = 2
  • Output: 4
  • Explanation: [1,2]

Constraints:

  • 1 <= n <= 5 * 104

Solution:

We can approach it using a Depth-First Search (DFS)-like strategy.

Key Insights:

  • Lexicographical order is essentially a pre-order traversal over a virtual n-ary tree, where the root node starts at 1, and each node has up to 9 children, which are formed by appending digits (0 to 9).
  • We can simulate this pre-order traversal by starting with 1 and repeatedly appending numbers, ensuring we don't exceed the given n.

Approach:

  1. Start with the number 1 and attempt to go deeper by multiplying by 10 (i.e., the next lexicographical number with the next digit).
  2. If going deeper (multiplying by 10) is not possible (i.e., exceeds n), increment the number, ensuring that it doesn’t introduce an invalid jump across tens (i.e., going from 19 to 20).
  3. We backtrack when the current number cannot be extended further and move to the next valid number.
  4. Continue until all numbers up to n are processed.

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]
登录后复制

Input: n = 2

  1. Start at 1.
  2. Move to 2.

Output:

[1, 2]
登录后复制

Time Complexity:

  • O(n) since each number from 1 to n is processed exactly once.

Space Complexity:

  • O(1) extra space is used (disregarding the space used for the result array).

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:

  • LinkedIn
  • GitHub

以上是. Lexicographical Numbers的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板