diff options
author | Jack Sangdahl <jack@pngu.org> | 2024-06-28 14:53:45 -0600 |
---|---|---|
committer | Jack Sangdahl <jack@pngu.org> | 2024-06-28 14:53:45 -0600 |
commit | f0f19d97c5ac7b87520e1c92eaead1f36b470312 (patch) | |
tree | 69bd4924d6fb3ac37a19d5bb7881e0fade42579f /lexicographical_numbers.py | |
parent | 6f930ea50d5d4c75483b0224942a3a9a288c86de (diff) | |
download | leetcode-f0f19d97c5ac7b87520e1c92eaead1f36b470312.tar.gz leetcode-f0f19d97c5ac7b87520e1c92eaead1f36b470312.zip |
386. lexicographical numbers
Diffstat (limited to 'lexicographical_numbers.py')
-rw-r--r-- | lexicographical_numbers.py | 31 |
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)) |