Google
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)