題目敘述 386. Lexicographical Numbers
給定一個數字n，請實作一個字典序(Lexical order)排列的報數機，
依字典序輸出所有1~n的數字。
你必須實現一個O(n) time線性時間，O(1) extra space常數額外空間的演算法。
測試範例
Example 1:
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2
Output: [1,2]
約束條件
Constraints:
1 <= n <= 5 * 10^4
n值介於 1 ~ 五萬 之間。
演算法 根據字典序生成1~n數列
currentNum 從1開始出發，
每回合迭代的時候，
測試當下的currentNum能不能擴張10倍，而且不超過n？
如果可以，就擴張10倍，依照字典序生成相關的數字。
如果不行，則縮減到原有的合法範圍內，每次累加1，生成由小到大遞增的數字。
Python 程式碼
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
result = []
cur = 1
for _ in range(n):
result.append( cur )
if cur * 10 <= n:
# Keep growing, start with 1...
cur = cur * 10
else:
# Keep shrinking if current number's last digit is 9, or current number is too big
while (cur % 10 == 9) or (cur >= n ):
cur = cur // 10
# Go to next number
cur = cur + 1
return result
Golang 程式碼
func lexicalOrder(n int) []int {
result := []int{}
currentNum := 1
for i := 0 ; i < n ; i++{
result = append(result, currentNum)
if currentNum * 10 <= n{
// Keep growing, start with 1...
currentNum = currentNum * 10
}else{
// Keep shrinking if current number's last digit is 9, or current number is too big
for (currentNum % 10 == 9) || (currentNum >= n ){
currentNum = currentNum / 10
}
// Go to next number
currentNum = currentNum + 1
}
}
return result
}
複雜度分析
時間複雜度: O(n)
依照字典序生成1~n的所有數字，每個數字只會生成一次。
空間複雜度: O(1)
除了題目輸出指定的result陣列以外，
其他用到的都是固定尺寸的臨時變數，所需額外空間為O(1)
