Code & Func

第73天。

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

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

1
vector<int> lexicalOrder(int n) {
2
    vector<int> res(n);
3
    int cur = 1;
4
    for (int i = 0; i < n; i++) {
5
        res[i] = cur;
6
        if (cur * 10 <= n) {
7
            cur *= 10;
8
        } else {
9
            if (cur >= n)
10
                cur /= 10;
11
            cur += 1;
12
            while (cur % 10 == 0)
13
                cur /= 10;
14
        }
15
    }
2 collapsed lines
16
    return res;
17
}