aboutsummaryrefslogtreecommitdiff
path: root/lexicographical_numbers.py
diff options
context:
space:
mode:
authorJack Sangdahl <jack@pngu.org>2024-06-28 14:53:45 -0600
committerJack Sangdahl <jack@pngu.org>2024-06-28 14:53:45 -0600
commitf0f19d97c5ac7b87520e1c92eaead1f36b470312 (patch)
tree69bd4924d6fb3ac37a19d5bb7881e0fade42579f /lexicographical_numbers.py
parent6f930ea50d5d4c75483b0224942a3a9a288c86de (diff)
downloadleetcode-f0f19d97c5ac7b87520e1c92eaead1f36b470312.tar.gz
leetcode-f0f19d97c5ac7b87520e1c92eaead1f36b470312.zip
386. lexicographical numbers
Diffstat (limited to 'lexicographical_numbers.py')
-rw-r--r--lexicographical_numbers.py31
1 files changed, 31 insertions, 0 deletions
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))