lexicographical-number.py (1086B)
1 class Solution: 2 def lexicalOrder(self, n: int) -> list[int]: 3 # ideas: 4 # sorting 5 # too slow 6 # some sort of stateless traversal 7 # prior is something, what's next given prior and max? 8 # how? 9 # it's the last number with 0 added to the right side 10 # if this is too large, increment the final digit 11 # if that's too large, increment the digit to the left and drop rightmost? 12 prior = 1 13 res = [prior] 14 for _ in range(0,n-1): 15 if prior * 10 <= n: 16 res.append(prior*10) 17 prior *= 10 18 continue 19 if prior + 1 <= n and (prior + 1) // 10 == prior // 10: 20 res.append(prior+1) 21 prior += 1 22 continue 23 24 prior = prior // 10 25 while (prior + 1) // 10 != prior // 10: 26 prior = prior // 10 27 28 prior += 1 29 res.append(prior) 30 return res