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
This Java solution adopts an iterative logic to determine the next candidate number in the lexicographical progression by observing digit endings and adjusting accordingly.