# 386. 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.

``````class Solution {
public:
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;
}
};
``````

``````class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> res;
for (int i = 1; i <= 9; ++i) {
helper(i, n, res);
}
return res;
}
void helper(int cur, int n, vector<int>& res) {
if (cur > n) return;
res.push_back(cur);
for (int i = 0; i <= 9; ++i) {
if (cur * 10 + i <= n) {
helper(cur * 10 + i, n, res);
} else break;
}
}
};
``````

https://discuss.leetcode.com/topic/55131/ac-240ms-c-solution

https://discuss.leetcode.com/topic/55091/java-recursion-backtracking-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation