一、题目描述
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.
二、分析
Observations:
For any given digit k, the lexical order of all numbers starting with digit k looks like:
k, k10, k10^2, k10^3, ..., k10^p +1, k10^p + 2, ..., k10^(p-m) +1, ...
For example, the sequence of numbers starting with digit 1 will be like (with n = 2000):
1, 10, 100, 1000, 1001, 1002, ..., 1009, 101, 1010, 1011, 1012, ..., 1019, 102, 1020, ..., 1099, 11, 110, 1100, 1101, ...
Through the observations above, a valid sub-sequence can only be started when we encounter 1) we cannot append more zeroes to the previous number; or 2) a number that ends in consecutive '9's.
三、解答
1 class Solution {
2 public:
3 vector<int> lexicalOrder(int n) {
4 vector<int> rs;
5
6 int i = 1, j;
7 int k;
8 for(;;)
9 {
10 // append as many zeroes as possible to the previous number
11 for(k = 0; i*pow(10,k) <= n; ++k) rs.push_back(i*pow(10,k));
12
13 // count continuously until we reach a number that ends with consecutive '9's
14 for(j = rs.back()+1; j <= n && (j % 10) != 0; ++j) rs.push_back(j);
15
16 // backtrace
17 if(j % 10 == 0)
18 {
19 j--;
20 }
21 else
22 {
23 j /= 10;
24 }
25
26 // find the last non-'9' digit
27 while(j % 10 == 9) j /= 10;
28
29 // start a new sub-sequence
30 i = j+1;
31
32 if(rs.size() >= n) break;
33 }
34
35 return rs;
36 }
37 };