题目要求
1
2
3
4
5
| Given an integer n, return 1 - n in 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.
|
将1n这n个数字按照字母序排序，并返回排序后的结果。
即如果n=13，则113的字母序为1,10,11,12,13,2,3,4,5,6,7,8,9
思路和代码
这题其实要求我们将数字是做字母来进行排序，因此当我们排序的时候可以看到，假如已知当前的数字为i，则它首先后一位数字应当是**(i x 10)，如果(i x 10)大于n，再考虑i+1**, 如果i+1也大于n，此时再考虑**(i/10)+1**。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public List<Integer> lexicalOrder(int n) {
List<Integer> result = new ArrayList<Integer>();
for(int i = 1 ; i<=9 ; i++) {
lexicalOrder(n, i, result);
}
return result;
}
public void lexicalOrder(int n, int cur, List<Integer> result) {
if(cur > n) return;
result.add(cur);
for(int i = 0 ; i <=9 ; i++) {
lexicalOrder(n, cur*10+i, result);
}
}
|