題目描述
給定一個整數 n, 傳回從 1 到 n 的字典順序。
例如，給定 n = 13，傳回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
請盡可能的優化算法的時間複雜度和空間複雜度。 輸入的資料 n 小于等于 5,000,000。
題解
排序法
首先把 1 到 n 所有整數的字元串形式放進數組，然後對這個字元串數組進行排序，最後把所有字元串轉換成對應的整數就行了。
時間複雜度是
，空間複雜度是
。
字典樹法
還可以按從小到大順序直接生成所有整數，首先觀察如下的字典樹：
字典樹
可以看出來，這是一棵 10 叉的字典樹，第一層根節點，第二層沒有 0 （因為不能有前導 0 ），後面的每一層都是在上一層的基礎上添加一位 0 到 9 。
而如果按照前序周遊的順序周遊這棵樹，得到的整數序列就是字典序從小到大的。但是這棵樹深度是沒有限制的啊，是以如果周遊到的數字 x 大于 n 的話，就要結束周遊，回溯到上一層。
時間複雜度是
，空間複雜度是
。
代碼
排序法（c++）
class
排序法（python）
class
字典樹法（c++）
class
字典樹法（python）
class
後記
字典序法的遞歸需要耗費更大的空間，而在實際運作中， python 代碼排序法的運作速度甚至比字典序法更快，這說明了 python 遞歸是真的慢。