386. lexicographical numbers

Posted on |

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.

这道题可以用DFS做,但是会超时.实际上找到lexicographical sort的规律就可以写出O(n)的解法.如果我们输入1004,返回的vector中依次出现的应该是

1
[1, 10, 100, 1000, 1001, 1002...]

可以发现规律是先一直在后面补0直到不能再补,然后逐渐加1.之后要考虑edge case:

  • 如果正好到了1004的时候,如果我们再加1会溢出.这个时候下一个值应该是101,即将当前的数右移一位.
  • 如果下一个数进位的话,要一直回退到第一个不是0的位置: 799 + 1 = 800,而799的下一个数应该是 800 / 100 = 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ret(n);
        int cur = 1;
        for(int i = 0; i < n; i++){
            ret[i] = cur;
            if(cur * 10 <= n){
                cur *= 10;
            }
            else{
                if(cur >= n){
                    cur /= 10;
                }
                cur += 1;
                while(cur % 10 == 0){
                    cur /= 10;
                }
            }
        }
        return ret;
    }
};