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]的所有数字按照字典顺序来排列，题目中也给了我们字典顺序的例子。那么我们需要重新排序，我最开始想到的方法是重写sort方法的comparator，思路是把所有数字都转为字符串，然后两个字符串按位相比，然后排好序后再转回数字，这种方法通过不了OJ的大集合，说明本题不是想考我们这种方法。我在论坛里看到大家普遍使用的是下面这种方法，学习了一下，感觉思路十分巧妙，估计我自己肯定想不出来。这种思路是按个位数遍历，在遍历下一个个位数之前，先遍历十位数，十位数的高位为之前的个位数，只要这个多位数并没有超过n，就可以一直往后遍历，如果超过了，我们除以10，然后再加1，如果加1后末尾形成了很多0，那么我们要用个while循环把0都去掉，然后继续运算，参见代码如下：
解法一：
class Solution { public: vector<int> lexicalOrder(int n) { vector<int> res(n); int cur = 1; for (int i = 0; i < n; ++i) { res[i] = cur; if (cur * 10 <= n) { cur *= 10; } else { if (cur >= n) cur /= 10; cur += 1; while (cur % 10 == 0) cur /= 10; } } return res; } };
下面这种方法是上面解法的递归形式，思路并没有什么不同，参见代码如下：
解法二：
class Solution { public: vector<int> lexicalOrder(int n) { vector<int> res; for (int i = 1; i <= 9; ++i) { helper(i, n, res); } return res; } void helper(int cur, int n, vector<int>& res) { if (cur > n) return; res.push_back(cur); for (int i = 0; i <= 9; ++i) { if (cur * 10 + i <= n) { helper(cur * 10 + i, n, res); } else break; } } };
本文转自博客园Grandyang的博客，原文链接：字典顺序的数字[LeetCode] Lexicographical Numbers ，如需转载请自行联系原博主。
![[leetcode/lintcode 题解] 国内大厂面试真题详解：外星人字典](https://ucc.alicdn.com/pic/developer-ecology/839eb0f73cd341858df816f6fbf00df0.png?x-oss-process=image/resize,h_160,m_lfit)
![[leetcode/lintcode 题解]算法面试真题详解：外星人字典](https://ucc.alicdn.com/pic/developer-ecology/b454768675214153bbe1af8a590e4376.png?x-oss-process=image/resize,h_160,m_lfit)