386 Lexicographical Numbers 字典序排數(shù)

Description:
Given an integer n, return 1 - n in lexicographical order.

Example:

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

題目描述:
給定一個整數(shù) n, 返回從 1 到 n 的字典順序。

示例 :

給定 n = 13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

請盡可能的優(yōu)化算法的時間復雜度和空間復雜度。 輸入的數(shù)據(jù) n 小于等于 5,000,000。

思路:

1. 先排序字符串, 然后將排序好的字符串轉換為整數(shù)
   時間復雜度O(nlgn), 空間復雜度O(n)
2. 設置一個指針
   比如需要放 1-130
   指針開始指向 1, 下一個應該放 10, 所以比較指針 * 10和 n的大小關系
   指針自乘 10直到超過 n
   這時已經(jīng)放入了 [1, 10, 100],
   由于 100 * 10 > 130, 此時下一個應該是 11, 這時指針需要從 100移動到 11, 比較指針和 n的大小, 指針超過 n就自除 10, 然后自增直到 20, 下一個數(shù)為2, 所以當?shù)臀皇?0的時候, 需要去掉
   時間復雜度O(nlgn), 空間復雜度O(1)

代碼:
C++:

class Solution 
{
public:
    vector<int> lexicalOrder(int n) 
    {
        vector<int> result(n);
        int cur = 1;
        for (int i = 0; i < n; i++)
        {
            result[i] = cur;
            if (cur * 10 <= n) cur *= 10;
            else
            {
                if (cur >= n) cur /= 10;
                ++cur;
                while (!(cur % 10)) cur /= 10;
            }
        }
        return result;
    }
};

Java:

class Solution {
    public List<Integer> lexicalOrder(int n) {
        String list[] = new String[n];
        for (int i = 1; i < n + 1; i++) list[i - 1] = String.valueOf(i);
        Arrays.sort(list);
        List<Integer> result = new ArrayList<>(n);
        for (String s : list) result.add(Integer.valueOf(s));
        return result;
    }
}

Python:

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        return sorted(range(1, n + 1), key=str)