aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-07 20:53:32 -0600
committerJack Sangdahl <[email protected]>2025-06-07 20:53:32 -0600
commitd3382a11112d2dfe31b2d156c73d07d1ee213a97 (patch)
treee77bf450ea209365ff123ec00402cfa8b4b3607c
parent38025a19a342cb266e766e8cf9aeadfccd8c68ae (diff)
downloadleetcode-d3382a11112d2dfe31b2d156c73d07d1ee213a97.tar.gz
leetcode-d3382a11112d2dfe31b2d156c73d07d1ee213a97.zip
386. lexicographical numbersHEADmaster
-rw-r--r--lexicographical_numbers.c33
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;
}