aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lexicographical_numbers.c44
-rw-r--r--lexicographical_numbers.cpp19
-rw-r--r--lexicographical_numbers.py31
3 files changed, 93 insertions, 1 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);
+}
diff --git a/lexicographical_numbers.cpp b/lexicographical_numbers.cpp
index 55e9fe3..ab48ce5 100644
--- a/lexicographical_numbers.cpp
+++ b/lexicographical_numbers.cpp
@@ -1,6 +1,12 @@
-// dnw
+// 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.
+ */
+
class Solution {
public:
vector<int> ans;
@@ -24,3 +30,14 @@ private:
}
}
};
+
+int main() {
+ Solution obj;
+ vector<int> lo1 = obj.lexicalOrder(13), lo2 = obj.lexicalOrder(2);
+ for (int i = 0; i < lo1.size(); 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 < lo2.size(); i++)
+ printf("%d ", lo2[i]); // expect: [1,2]
+ printf("\n");
+}
diff --git a/lexicographical_numbers.py b/lexicographical_numbers.py
new file mode 100644
index 0000000..0ab6d4e
--- /dev/null
+++ b/lexicographical_numbers.py
@@ -0,0 +1,31 @@
+# 386. Lexicographical Numbers
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def lexicalOrder(self, n):
+ """
+ :type n: int
+ :rtype: List[int]
+ """
+ ans = [1]
+ while len(ans) < n:
+ tmp = ans[-1] * 10
+ while tmp > n:
+ tmp /= 10
+ tmp += 1
+ while tmp % 10 == 0:
+ tmp /= 10
+ ans.append(tmp)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.lexicalOrder(13))
+ print(obj.lexicalOrder(2))