Sponsored
Sponsored
The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.
Time Complexity: O(n), Space Complexity: O(1) (excluding the output array).
1#include <stdio.h>
2
3void dfs(int current, int n, int* result, int* index) {
4 if (current > n) return;
5 result[(*index)++] = current;
6 for (int i = 0; i <= 9; ++i) {
7 if (current * 10 + i > n) return;
8 dfs(current * 10 + i, n, result, index);
9 }
10}
11
12int* lexicalOrder(int n, int* returnSize) {
13 int* result = (int*)malloc(n * sizeof(int));
14 *returnSize = 0;
15 for (int i = 1; i < 10; ++i) {
16 dfs(i, n, result, returnSize);
17 }
18 return result;
19}
20
21int main() {
22 int n = 13;
23 int returnSize;
24 int* result = lexicalOrder(n, &returnSize);
25 for (int i = 0; i < returnSize; ++i) {
26 printf("%d ", result[i]);
27 }
28 free(result);
29 return 0;
30}This C implementation uses a helper function dfs to execute the depth-first search. It explores each tree node by multiplying the current number by 10 and adding digits from 0 to 9, ensuring the number remains within the limit n. The results are stored in an array which is printed in the main function.
This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.
Time Complexity: O(n), Space Complexity: O(1) (ignoring return array).
1#include <vector>
using namespace std;
vector<int> lexicalOrder(int n) {
vector<int> result;
int num = 1;
for (int i = 0; i < n; ++i) {
result.push_back(num);
if (num * 10 <= n) {
num *= 10;
} else {
while (num % 10 == 9 || num + 1 > n) {
num /= 10;
}
num++;
}
}
return result;
}
int main() {
int n = 13;
vector<int> result = lexicalOrder(n);
for (int num : result) {
cout << num << " ";
}
return 0;
}The C++ code iteratively selects the next number in lexicographical order, ensuring correct value jumps, and accounts for adjusting when reaching end-of-digit sequences by resetting to the next appropriate number.