diff options
Diffstat (limited to 'lexicographical_numbers.c')
-rw-r--r-- | lexicographical_numbers.c | 44 |
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); +} |