LeetCode 386 字典排序

题目描述

给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

思路

字典序其实就是按照ASCII码从小到大排序,在微信支付中用到过。其实Java中的API中提供了对应的方法，就是Collections.sort这个方法。使用Collections.sort()传入ArrayList，会采用默认的方式进行排序也就是字典序。

代码

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;
    }

结果