aboutsummaryrefslogtreecommitdiff
path: root/lexicographical_numbers.c
diff options
context:
space:
mode:
Diffstat (limited to 'lexicographical_numbers.c')
-rw-r--r--lexicographical_numbers.c44
1 files changed, 44 insertions, 0 deletions
diff --git a/lexicographical_numbers.c b/lexicographical_numbers.c
new file mode 100644
index 0000000..5823da1
--- /dev/null
+++ b/lexicographical_numbers.c
@@ -0,0 +1,44 @@
+// 386. Lexicographical Numbers
+#include "leetcode.h"
+
+/*
+ * given an integer 'n', return all the numbers in the range '[1, n]' sorted in
+ * lexicographical order. you must write an algorithm that runs in O(n) time
+ * 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);
+ }
+ *returnSize = k;
+ return ans;
+}
+
+int main() {
+ int rs1, rs2;
+ int *lo1 = lexicalOrder(13, &rs1), *lo2 = lexicalOrder(2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", lo1[i]); // expect: [1,10,11,12,13,2,3,4,5,6,7,8,9]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", lo2[i]); // expect: [1,2]
+ printf("\n");
+ free(lo1), free(lo2);
+}