diff options
author | Jack Sangdahl <[email protected]> | 2025-06-07 20:53:32 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-07 20:53:32 -0600 |
commit | d3382a11112d2dfe31b2d156c73d07d1ee213a97 (patch) | |
tree | e77bf450ea209365ff123ec00402cfa8b4b3607c | |
parent | 38025a19a342cb266e766e8cf9aeadfccd8c68ae (diff) | |
download | leetcode-d3382a11112d2dfe31b2d156c73d07d1ee213a97.tar.gz leetcode-d3382a11112d2dfe31b2d156c73d07d1ee213a97.zip |
-rw-r--r-- | lexicographical_numbers.c | 33 |
1 files changed, 14 insertions, 19 deletions
diff --git a/lexicographical_numbers.c b/lexicographical_numbers.c index 5823da1..2208599 100644 --- a/lexicographical_numbers.c +++ b/lexicographical_numbers.c @@ -7,27 +7,22 @@ * complexity and uses O(1) extra space. */ -void lex(int *res, int n, int i, int digit, int *k) { - if (!digit) - return; - for (int j = i * 10; j < (i + 1) * 10 && j <= n; j++) { - res[(*k)++] = j; - lex(res, n, j, digit - 1, k); - } -} - int *lexicalOrder(int n, int *returnSize) { - int *ans = (int *)malloc((n + 1) * sizeof(int)); - int tmp = n, max_digit = 0, k = 0; - while (tmp) { - tmp /= 10; - max_digit++; - } - for (int i = 1; i < 10 && i <= n; i++) { - ans[k++] = i; - lex(ans, n, i, max_digit, &k); + int *ans = (int *)malloc(n * sizeof(int)); + int curr = 1, k = 0; + for (int i = 0; i < n; i++) { + ans[i] = curr; + if (((curr << 3) + (curr << 1)) <= n) + curr = (curr << 3) + (curr << 1); + else { + if (curr >= n) + curr /= 10; + curr++; + while (!(curr % 10)) + curr /= 10; + } } - *returnSize = k; + *returnSize = n; return ans; } |