【leetcode】386 Lexicographical Numbers

发表于 | 分类于 ，

数字字典序排序

NO Pictures

描述

给定一个数 n ，对 1 ，2 ，3 ，… n 进行字典序排序。

样例

1
2
输入: 13
输出: 1  10  11  12  13  2   3   4   5   6   7   8   9

思路

最简单的方法，转成字符串，之后比较得出结果，这里有一些小小的问题，string 类型的 > 比较好像不对 “15”>”14” 输出的结果居然是 0 ,这里可以采用 sprintf 进行转换。代码 1 易于理解，但是会超时，代码 2 需要好好的理解。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> lexicalOrder(int n) {

        vector<int>a;
        for (int i = 1; i <= n; i++) {
            a.push_back(i);
        }
        auto cmp = [](int n1, int n2) {
            static char si[32] = { 0 }, sj[32] = { 0 };
            sprintf(si, "%d\0", n1);
            sprintf(sj, "%d\0", n2);
            return (strcmp(si, sj)<0);

        };

        sort(a.begin(), a.end(), cmp);

        return a;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> result;
        int cur = 1;
        while (result.size() < n) {
            for (; cur <= n; cur *= 10) {
                result.push_back(cur);
            }
            cur = cur / 10 + 1;
            for (; cur <= n && cur % 10 != 0; cur++) {
                result.push_back(cur);
            }
            for (; cur % 10 == 0; cur /= 10);

        }
        return result;
    }
};

参考

原题链接
参考链接