class Solution {
public:
vector<int> lexicalOrder(int n) {
}
};
386. 字典序排数
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例 1：
输入：n = 13 输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例 2：
输入：n = 2 输出：[1,2]
提示：
1 <= n <= 5 * 104原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 46 MB, 提交时间: 2022-11-16 12:42:40
class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
for (int i = 0, j = 1; i < n; i++) {
ans.add(j);
if (j * 10 <= n) {
j *= 10;
} else {
while (j % 10 == 9 || j + 1 > n) j /= 10;
j++;
}
}
return ans;
}
}
java 解法, 执行用时: 4 ms, 内存消耗: 46.1 MB, 提交时间: 2022-11-16 12:41:59
class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
for (int i = 1; i <= 9; i++) dfs(i, n);
return ans;
}
void dfs(int cur, int limit) {
if (cur > limit) return ;
ans.add(cur);
for (int i = 0; i <= 9; i++) dfs(cur * 10 + i, limit);
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 6.3 MB, 提交时间: 2022-11-16 12:40:40
func lexicalOrder(n int) []int {
ans := make([]int, n)
num := 1
for i := range ans {
ans[i] = num
if num*10 <= n {
num *= 10
} else {
for num%10 == 9 || num+1 > n {
num /= 10
}
num++
}
}
return ans
}
python3 解法, 执行用时: 44 ms, 内存消耗: 21.9 MB, 提交时间: 2022-11-16 12:36:34
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
nums = [i for i in range(1, n+1)]
return sorted(nums, key=lambda x: str(x))