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的字典序输出。

思路1：使用stl函数sort，更改比较函数，输出即可。由于输入数字较大，导致超时。

class Solution {public:    static bool cmp(const int& a, const int& b)    {        string s1 = to_string(a);        string s2 = to_string(b);        return s1 < s2;    }    vector
        
          lexicalOrder(int n) {        vector
         
           res;        for (int i = 1; i <= n; ++i)            res.push_back(i);        sort(res.begin(), res.end(), cmp);        return res;    }};
         
        

思路2：根据数字的特征值。

举个栗子：13

1-10-11-12-13

2

3

4

5

6

7

8

9

外循环1-9.内函数递归增加0-9进行计算，如果当前值超过了n，则直接返回，如果当前值不超过n，则放入结果数组res中。

class Solution {public:    vector
       
         lexicalOrder(int n) {        vector
        
          res;        for (int i = 1; i < 10; ++i)            find_next(i, n, res);        return res;    }        void find_next(int i, int n, vector
         
          & res)    {        if (i > n)            return;        res.push_back(i);        for (int j = 0; j < 10; ++j)            find_next(i*10+j, n, res);    }};
         
        
       

思路3：Python sorted函数。

class Solution:    def lexicalOrder(self, n):        """        :type n: int        :rtype: List[int]        """        return sorted(range(1, n+1), key=lambda x : str(x))