Lexicographical-Number

LeetCode

第73天。

今天的题目是Lexicographical Numbers:

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.

emmm，lexicographical是字典序的意思。

首先，这种有规律的题目一般用递归来写会比较简单（但是可能会超时），我们先找出它的规律，在不到n的时候，没加入一个数字i,我们就要看i*10 ~ i*10 + 9是否小于n,如果小于我们就把它加入，然后在递归的进行判断。

有一点需要注意的就是，它是从1开始的，所以我们一开始就要尝试的把1 ~ 9加入，而不是0 ~ 9：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> lexicalOrder(int n) {
    vector<int> ret;
    //lexicalOrder(ret,n,1);
    for(int i = 1;i < 10 && i <= n;i++) {
        ret.push_back(i);
        lexicalOrder(ret,n,i*10);
    }
    return ret;
}
void lexicalOrder(vector<int> &vec,int n,int base) {
    for(int i = 0;i < 10;i++,base++) {
        if (base > n){ return; }
        vec.push_back(base);
        lexicalOrder(vec,n,10*base);
    }
}

然后是在dicuss中看到的迭代解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}