问题描述

给定一个整数 n，以字母顺序返回 1-n 之间的数字。

比如：n = 13，那么返回 [1,10,11,12,13,2,3,4,5,6,7,8,9]。

要求优化算法，使用更少的时间和空间。注意：n 可能会很大。

想看英文的戳这里。

解题思路

这道题目叙述简单，题意也很清晰，按字母顺序排序即可。

比如按字母顺序， 10 是小于 2 的。因为按 ascii 码的值， 1 就比 2 小。所有以 1 开头的都小于以 2 开头的数字，无论 1 开头的数字有多大。

我的解法

我们可以试着写出结果，看看其规律。比如 n = 200。

// 以 1 开头的全部列举完
1,
10,100,101,102,...,109,
11,110,111,112,...,119,
12,120,121,122,...,129,
...
19,190,191,192,...199

// 以 2 开头
2,
20,200
21

// 以 3 开头
...


// 以 9 开头
...

以字母排序的特点就在于：需要将以 1 开头的数字（<=n）列举完之后，再开始排列 2 开头的。

从以下 1 的排布中，可以发现一些规律。

1, 10, 100, ..., 109, 11, 110, 111, ..., 119, ...

比如当前数字为 1，其乘以 10 后，继续往后数 10 个数字，10, 11, ..., 19。再需要从 10 开始重复该步骤，得到 100, 101, ..., 109；再从 100 开始重复该步骤，直至数字大于 n；再从 101 开始，继续这一过程。

说文字有点绕，看图吧。

image.png

理解这一思想后，代码实现就比较简单了。只需要将新生成的 10 个数插入到原数组当前指向的下一个位置，继续遍历即可。

比如原数组为 [1,2,3,4]，当前指向 1，那么插入后变为 [1,10,11,12,..,19,2,3,4]。往后遍历到 10，在 10 的后面插入 [100,...,109] 即可。

代码如下：

var lexicalOrder = function(n) {
    if (n < 1) {
        return []
    }

    // 初始化
    let list = []
    let i = 1

    // 数字最大以 9 开头    
    let count = n >= 9 ? 9 : n
    while (i <= count) {
        list.push(i)
        i += 1
    }

    let k = 0

    while (k <= list.length - 1) {
        // * 10
        const b = list[k] * 10
        let j = 0

        // 往后数 10 个数
        while (j < 10) {
            // 如果 < n
            if (b + j <= n) {
                // 将新生成的数插入原数组
                list.splice(k + 1 + j, 0, b + j)
            } else {
                break
            }

            j += 1
        }

        k += 1
    }

    return list
};

递归解法

和以上思路一致，使用递归实现，点此查看代码。

public class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for(int i=1;i<10;++i){
          dfs(i, n, res); 
        }
        return res;
    }
    
    public void dfs(int cur, int n, List<Integer> res){
        if(cur>n)
            return;
        else{
            res.add(cur);
            for(int i=0;i<10;++i){
                if(10*cur+i>n)
                    return;
                dfs(10*cur+i, n, res);
            }
        }
    }
}

奇妙解法

这种解法比较奇妙，通过计算待排的下一个数字来排序，时间复杂度 O(n)。

只包括以下三种计算：

乘以 10
加 1
除以 10

看代码比较清晰一些：

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 {
                // 比如 cur = n = 115, 那么 cur 又从 12 开始
                if (cur >= n) 
                    cur /= 10;
                cur += 1;
                
                // 比如 cur = 110，应该再从 11 开始
                while (cur % 10 == 0)
                    cur /= 10;
            }
        }
        return res;
    }
};