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       2       3 ...
  /\      /\      /\
10...19 20...29 30...39 ....

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList();

        for (int i = 1; i <= 9; i++) {
            findLexicalOrder(i, n, res);
        }
        return res;
    }

    public void findLexicalOrder(int curNum, int n, List<Integer> res) {
        if (curNum > n) {
            return;
        }
        res.add(curNum);

        for (int i = 0; i <= 9; i++) {
            findLexicalOrder(curNum * 10 + i, n, res);
        }
    }
}

(2) Iteration

思路: Iteration的方法同样是对树做preorder traversal，具体分成以下几个步骤:

• 往下 找到leftmost node

• 当我们找到leftmost node时，开始进行level order traversal, 比如10是树的leftmost node,则遍历10-19的数

• 当我们到达rightmost node的时候，我们需要返回上一层，然后对下一个树做preorder traversal

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList();

        int curNum = 1;
        for (int i = 1; i <= n; i++) {
            res.add(curNum);
            // Case 1: Traverse down to find lestmost node
            if (curNum * 10 <= n) {
                curNum *= 10;
            }
            // Case 2: leftmost node found, do level traversal
            else if (curNum % 10 != 9 && curNum + 1 <= n) {
                ++curNum;
            }
            else {
                // Case 3.1: we are at the rightmost node，traverse up to upper level
                while ((curNum / 10) % 10 == 9) {
                    curNum /= 10;
                } 
                // Case 3.2: prepare to do traversal for the next tree
                curNum = curNum / 10 + 1;
            }
        }
        return res;   
    }
}

3. Time & Space Complexity

(1) Recursion:时间复杂度O(n), 空间复杂度O(n), 递归深度是最大数的digit个数，比如100的话，digit个数是3

(2) Iteration: 时间复杂度O(n), 空间复杂度O(n)