leetcode 386. Lexicographical Numbers 前K个字典序数组 + 字典序排序

红太狼 2022-06-04 05:51 141阅读 0赞

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.

这道题就是做一个拓扑排序，可以使用排序来做，但是这个肯定会超时，最好使用循环来做，这是网上看的一个答案

建议和这一道题[leetcode 440. K-th Smallest in Lexicographical Order 第k个字典序的数字][leetcode 440. K-th Smallest in Lexicographical Order _k] 一起学习

这道题最直接跌方法就是直接比较排序，下面的这种做法我没想出来这么做，很棒的想法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    
    
    bool cmp(int a, int b)
    {
        return to_string(a) < to_string(b);
    }
    
    class Solution 
    {
    public:
        vector<int> lexicalOrder(int n)
        {
            vector<int> res(n,0);
            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;
        }
    
        vector<int> lexicalOrderBySort(int n) 
        {
            vector<int> res;
            for (int i = 1; i <= n; i++)
                res.push_back(i);
            sort(res.begin(), res.end(),cmp);
            return res;
        }
    };

[leetcode 440. K-th Smallest in Lexicographical Order _k]: http://blog.csdn.net/JackZhang_123/article/details/78770372