386. Lexicographical Numbers

原题

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.

提示 ： 提交代码后 ， 需要用简洁的语言解释一下代码思路 ~ 谢谢

历史题目和总结见公众号「每日一道算法题」

https://leetcode.com/problems/lexicographical-numbers/description/

题目解析

给定一个整数n，返回1到n的字典序排列。

例如，给定13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9]。

请优化你的算法，使用更少的时间与空间。输入规模可能会达到5,000,000。

什么是字典序

设想一本英语字典里的单词，何者在前何者在后？

显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。