题目
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.
答案
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> list = new ArrayList<>();
int cnt = n - 1;
int curr = 1;
list.add(1);
while(cnt-- >= 1) {
if(curr * 10 <= n) {
// Always try to append 0 to the end of number if possible
curr = curr * 10;
}
else if(curr % 10 != 9 && curr + 1 <= n) {
// If you can't add 0s, add 1!
curr++;
}
else {
// In this case, try to find a number with smaller lexicographical order
while((curr / 10) % 10 == 9) {
curr = curr / 10;
}
curr = curr / 10 + 1;
}
list.add(curr);
}
return list;
}
}
