386. Lexicographical Numbers
Đề Bài
Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.
You must write an algorithm that runs in O(n) time and uses O(1) extra space.
Example 1:
Input: n = 13 Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2 Output: [1,2]
Constraints:
1 <= n <= 5 * 104
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0386-lexicographical-numbers.cpp
class Solution {
private:
vector<int> ans;
int limit;
public:
void dfs(int num) {
if (num > limit) {
return;
}
ans.push_back(num);
for (int suff = 0; suff <= 9; suff++) {
dfs(num * 10 + suff);
}
}
vector<int> lexicalOrder(int n) {
limit = n;
for (int num = 1; num <= 9; ++num) {
dfs(num);
}
return ans;
}
};
Python
0386-lexicographical-numbers.py
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
return sorted(list(range(1, n + 1)), key = lambda num: str(num))