leetcode 386. Lexicographical Numbers

最新推荐文章于 2025-05-20 19:46:55 发布

liqinzhe223

最新推荐文章于 2025-05-20 19:46:55 发布

阅读量199

点赞数

分类专栏： leetcode

本文链接：https://blog.csdn.net/liqinzhe11/article/details/79638767

版权

leetcode 专栏收录该内容

280 篇文章

订阅专栏

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

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.

思路是：

1->10->100...一直到大于了n

10->11->12..18->19->20(这个地方20就不行，需要变成2)

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