386 Lexicographical Numbers

386. Lexicographical Numbers​
1. Question
Given an integern, return 1 -nin lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.
2. Implementation
(1) Recursion
思路: 可以将数字排列成一个如下树状的结构, 这题的本质就是对这个树做preorder traversal
1
  1       2       3 ...
2
  /\      /\      /\
3
10...19 20...29 30...39 ....
Copied!
1
class Solution {
2
    public List<Integer> lexicalOrder(int n) {
3
        List<Integer> res = new ArrayList();
4
​
5
        for (int i = 1; i <= 9; i++) {
6
            findLexicalOrder(i, n, res);
7
        }
8
        return res;
9
    }
10
​
11
    public void findLexicalOrder(int curNum, int n, List<Integer> res) {
12
        if (curNum > n) {
13
            return;
14
        }
15
        res.add(curNum);
16
​
17
        for (int i = 0; i <= 9; i++) {
18
            findLexicalOrder(curNum * 10 + i, n, res);
19
        }
20
    }
21
}
Copied!
(2) Iteration
思路: Iteration的方法同样是对树做preorder traversal，具体分成以下几个步骤:
往下 找到leftmost node
当我们找到leftmost node时，开始进行level order traversal, 比如10是树的leftmost node,则遍历10-19的数
当我们到达rightmost node的时候，我们需要返回上一层，然后对下一个树做preorder traversal
1
class Solution {
2
    public List<Integer> lexicalOrder(int n) {
3
        List<Integer> res = new ArrayList();
4
​
5
        int curNum = 1;
6
        for (int i = 1; i <= n; i++) {
7
            res.add(curNum);
8
            // Case 1: Traverse down to find lestmost node
9
            if (curNum * 10 <= n) {
10
                curNum *= 10;
11
            }
12
            // Case 2: leftmost node found, do level traversal
13
            else if (curNum % 10 != 9 && curNum + 1 <= n) {
14
                ++curNum;
15
            }
16
            else {
17
                // Case 3.1: we are at the rightmost node，traverse up to upper level
18
                while ((curNum / 10) % 10 == 9) {
19
                    curNum /= 10;
20
                } 
21
                // Case 3.2: prepare to do traversal for the next tree
22
                curNum = curNum / 10 + 1;
23
            }
24
        }
25
        return res;   
26
    }
27
}
Copied!
3. Time & Space Complexity
(1) Recursion:时间复杂度O(n), 空间复杂度O(n), 递归深度是最大数的digit个数，比如100的话，digit个数是3
(2) Iteration: 时间复杂度O(n), 空间复杂度O(n)

544 Output Contest Matches

Last modified 2yr ago

Copy link

Contents

386. Lexicographical Numbers

1. Question

2. Implementation

3. Time & Space Complexity

386. Lexicographical Numbers​

1. Question

2. Implementation

3. Time & Space Complexity

386. Lexicographical Numbers