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).
1using System;
2using System.Collections.Generic;
3
4public class LexicalOrderDFS {
5 public void DFS(int current, int n, IList<int> result) {
6 if (current > n) return;
7 result.Add(current);
8 for (int i = 0; i <= 9; ++i) {
9 if (current * 10 + i > n) return;
10 DFS(current * 10 + i, n, result);
11 }
12 }
13
14 public IList<int> LexicalOrder(int n) {
15 IList<int> result = new List<int>();
16 for (int i = 1; i < 10; ++i) {
17 DFS(i, n, result);
18 }
19 return result;
20 }
21
22 public static void Main(string[] args) {
23 LexicalOrderDFS obj = new LexicalOrderDFS();
24 int n = 13;
25 IList<int> result = obj.LexicalOrder(n);
26 foreach (int num in result) {
27 Console.Write(num + " ");
28 }
29 }
30}This C# solution uses a List to hold results and a recursive function DFS to perform a depth-first search to generate lexicographical numbers up to n.
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.