▶循序漸進 實作報數機_Lexicographical Numbers_Leetcode #386

Jossuha Théophile on Unsplash

題目敘述 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)

Reference

[1] Lexicographical Numbers - LeetCode