问题描述
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.
public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer>list=new ArrayList<Integer>(n);
if(n<=9){
for(int i=1;i<=n;i++){
list.add(i);
}
}
else{
for(int i=1;i<=9;i++){
list.add(i);
doAdd(list, i, n);//每次doAdd都是把以i开头的数字都加入List中
}
}
return list;
}
public static void doAdd(List<Integer>list,int start,int n){
int moreBit=start*10;
if(moreBit<=n){
int ceil=n-moreBit;
int ans;
ceil=ceil>9?9:ceil;
for(int i=0;i<=ceil;i++){
ans=moreBit+i;
list.add(ans);
doAdd(list, ans, n);
}
}
}
}