問(wèn)題：
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.
思路：
給出一個(gè)整數(shù)n疗我，返回 1 到 n 的詞典順序。
比如南捂，給出13吴裤，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9]。
請(qǐng)優(yōu)化你的代碼來(lái)使用更少的時(shí)間和空間黑毅。輸入范圍會(huì)達(dá)到5000000嚼摩。
思路：
問(wèn)題的關(guān)鍵在于理清“詞典順序”是什么樣的钦讳。
詞典順序就是10比2靠前矿瘦，101比11靠前，110比11靠后愿卒，你可以簡(jiǎn)單的嘗試一下把數(shù)字都轉(zhuǎn)換成字符串?dāng)?shù)組缚去，然后對(duì)字符串?dāng)?shù)組進(jìn)行 Arrays.sort()，就會(huì)得到字符串下詞典順序的數(shù)字琼开。但是這個(gè)方法因?yàn)橛昧伺判蛞捉幔菚?huì)超時(shí)的。
所以我們的做法大致順序如下：
1柜候、如果一個(gè)數(shù)乘以十以后沒有超過(guò)n搞动，那它后面緊挨著的應(yīng)該是它的十倍，比如1,10,100渣刷。
2鹦肿、如果不滿足1，那就應(yīng)該是直接加一辅柴，比如n為13的時(shí)候箩溃，前一個(gè)數(shù)為12，120超過(guò)了n碌嘀，那接著的應(yīng)該是13涣旨。但是這里要注意如果前一個(gè)數(shù)的個(gè)位已經(jīng)是9或者是它就是n了，那就不能加一了股冗，比如 n = 25霹陡，前一個(gè)數(shù)為19，下一個(gè)數(shù)應(yīng)該為2而不是19+1=20。25的下一個(gè)也沒有26了烹棉。
3惠呼、如果不滿足2，比如19后面應(yīng)該接2而不是20峦耘，這時(shí)候應(yīng)該將19除以10再加一剔蹋，比如n=500，399的下一個(gè)應(yīng)該是4辅髓，那就是除以十泣崩，個(gè)位還是9，繼續(xù)除以10洛口，得到3矫付，加一得到4。
將上面的過(guò)程整理成代碼就可以了第焰，循環(huán)的次數(shù)就是n买优，也就是總個(gè)數(shù)。
代碼（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
