LeetCode题目链接链接

[https://leetcode-cn.com/problems/lexicographical-numbers/]

题目

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

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

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

分析

首先。比较简单粗暴的方法，因为是字典顺序，把所有数字都转化为为字符串，然后字符串排序，排序后重新转化为Integer
代码如下

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1;i <= n;i++) {
            StringBuilder builder = new StringBuilder();
            builder.append(i);
            list.add(builder.toString());
        }
        
        Collections.sort(list);
        
        List<Integer> ans = new ArrayList<>();
        for (String s : list) {
            ans.add(Integer.parseInt(s));
        }
        
        return ans;
    }
}

效果如下

image.png

第二种解法

输入
10
输出
[1,10,2,3,4,5,6,7,8,9]

输入
101
输出
[1,10,100,101,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,51,52,53,54,55,56,57,58,59,6,60,61,62,63,64,65,66,67,68,69,7,70,71,72,73,74,75,76,77,78,79,8,80,81,82,83,84,85,86,87,88,89,9,90,91,92,93,94,95,96,97,98,99]
根据代码找规律吧

class Solution {
   public List<Integer> lexicalOrder(int n) {
        int cur=1;
            List<Integer> sort = new ArrayList<>(n);
            for(int i=0;i<n;i++)
            {
               sort.add(cur);
                if(cur*10<=n){
                    cur*=10;
                  }
                else
                {
                    if(cur>=n)
                        cur/=10;
                    cur+=1;
                    while(cur%10==0)
                        cur/=10;
                }
            }

            return sort ;
    }
}