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.

思路

题目的要求很简单，需要我们将一堆数字用字符串排序的方法来输出。

我们可以尝试利用Java里面的内建排序方法。然而懒人并没有好报，在49999的用例就超时了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<String> list = new ArrayList<String>();
        List<Integer> integers = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++){
            list.add(Integer.toString(i));
        }
        list.sort(String::compareTo);
        for (String s: list){
            integers.add(Integer.parseInt(s));
        }
        return integers;
    }
}

我们其实还可以利用深度优先遍历来做的。可是还是超时！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public List<Integer> DFS(int n, int start){
        List<Integer> list = new ArrayList<Integer>();
        int num = start * 10;
        for (int i = 0; i < 10; i++){
            int tmp = num + i;
            if (num + i <= n){
                list.add(num + i);
                list.addAll(DFS(n, tmp));
            }
        }
        return list;
    }
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<Integer>();
        int loop = 9;
        if (n <= 9) loop = n;
        for (int i = 1; i <= loop; i++){
            list.add(i);
            list.addAll(DFS(n, i));
        }
        return list;
    }
}

Java过不了，那就试试C++吧。擦着边AC了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> DFS(int n, int start){
        vector<int> list;
        int num = start * 10;
        for (int i = 0; i < 10; i++){
            int tmp = num + i;
            if (num + i <= n){
                list.push_back(num + i);
                vector<int> tmplist = DFS(n, tmp);
                list.insert(list.end(),tmplist.begin(),tmplist.end());
            }
        }
        return list;
    }
    vector<int> lexicalOrder(int n) {
        vector<int> list;
        int loop = 9;
        if (n <= 9) loop = n;
        for (int i = 1; i <= loop; i++){
            list.push_back(i);
            vector<int> tmplist = DFS(n, i);
            list.insert(list.end(),tmplist.begin(),tmplist.end());
        }
        return list;
    }
};