leetCode179|字典序排数

码农王同学

发布于 2021-02-02 13:50:30

5310

发布于 2021-02-02 13:50:30

文章被收录于专栏：后端Coder

一，字典序排数

1，问题简述

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

2，示例描述

例如，

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

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

3，题解思路

字符串比较函数

4，题解程序

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public  class LexicalOrderTest2 {
    public static void main(String[] args) {
        int n = 13;
        List<Integer> list = lexicalOrder(n);
        System.out.println("list = " + list);

    }

    public static List<Integer> lexicalOrder(int n) {
        List<String> list = IntStream
                .rangeClosed(1, n)
                .mapToObj(String::valueOf)
                .sorted(String::compareTo)
                .collect(Collectors.toCollection(() -> new ArrayList<>(n)));

        return list.stream().mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
    }

    public static List<Integer> lexicalOrder2(int n) {
        List<String> list = new ArrayList<>(n);
        for (int i = 1; i <= n; i++) {
            list.add(String.valueOf(i));
        }
        list.sort(String::compareTo);
        return list.stream().mapToInt(Integer::parseInt).boxed().collect(Collectors.toList());
    }
}