[LeetCode386]Lexicographical Numbers（n以内的数字按字典序输出）

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.

方法一：递归版（比较容易想到）
class Solution {
public:vector<int> lexicalOrder(int n) {vector<int> ans(n);for(int i=1; i<=9; i++){if(i>n) break;solve(i, n, ans);}return ans;}void solve(int cur, int n, vector<int>& ans){ans.push_back(cur);for(int i=0; i<=9; i++){int tmp=cur*10+i;if(tmp>n) return ;solve(tmp, n, ans);}}
};
方法二：非递归版（比较难想）
class Solution {
public:vector<int> lexicalOrder(int n) {vector<int> ans;int cur=1;for(int i=0; i<n; i++){ans.push_back(cur);if(cur*10<=n) cur*=10;else{if(cur>=n) cur/=10;cur+=1;while(cur%10==0) cur/=10;}}return ans;}
};