LeetCode笔记：386. Lexicographical
问题：
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.
思路：
给出一个整数n，返回 1 到 n 的词典顺序。
比如，给出13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9]。
请优化你的代码来使用更少的时间和空间。输入范围会达到5000000。
思路：
问题的关键在于理清“词典顺序”是什么样的。
词典顺序就是10比2靠前，101比11靠前，110比11靠后，你可以简单的尝试一下把数字都转换成字符串数组，然后对字符串数组进行 Arrays.sort()，就会得到字符串下词典顺序的数字。但是这个方法因为用了排序，是会超时的。
所以我们的做法大致顺序如下：
1、如果一个数乘以十以后没有超过n，那它后面紧挨着的应该是它的十倍，比如1,10,100。
2、如果不满足1，那就应该是直接加一，比如n为13的时候，前一个数为12，120超过了n，那接着的应该是13。但是这里要注意如果前一个数的个位已经是9或者是它就是n了，那就不能加一了，比如 n = 25，前一个数为19，下一个数应该为2而不是19+1=20。25的下一个也没有26了。
3、如果不满足2，比如19后面应该接2而不是20，这时候应该将19除以10再加一，比如n=500，399的下一个应该是4，那就是除以十，个位还是9，继续除以10，得到3，加一得到4。
将上面的过程整理成代码就可以了，循环的次数就是n，也就是总个数。
代码（Java）：
public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<Integer>();
int cur = 1;
for (int i = 1; i <= n; i++) {
res.add(cur);
if (cur * 10 <= n) {
cur = cur * 10;
} else if (cur % 10 != 9 && cur + 1 <= n) {
cur++;
} else {
while ((cur / 10) % 10 == 9) {
cur = cur / 10;
}
cur = cur / 10 + 1;
}
}
return res;
}
}
合集：https://github.com/Cloudox/LeetCode-Record
