386. 字典序排數(shù)

給你一個(gè)整數(shù) n ，按字典序返回范圍 [1, n] 內(nèi)所有整數(shù)。

你必須設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為 O(n) 且使用 O(1) 額外空間的算法。

?

示例 1：

輸入：n = 13

輸出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：

輸入：n = 2

輸出：[1,2]

class?Solution:

????def?lexicalOrder(self,?n:?int)?->?List[int]:

????????res=[0]*n

????????num=1

????????for?i?in?range(n):

????????????res[i]=num

????????????if?num*10<=n:

????????????????num*=10

????????????else:

????????????????while?num%10==9?or?num+1>n:

????????????????????num//=10

????????????????num+=1

????????return?res

#?判斷邊界條件，先看*10是否滿足條件，滿足則進(jìn)位，不滿足則+1，+1的前提是不為9或不超距