leetCode-386:Lexicographical Numbers

问题描述

给定一个整数 n，要求按字典序对 1 到 n 进行排序。题目链接：**点我**

样例输入输出

输入：13

输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

输入：4

输出：[1,2,3,4]

问题解法

对数字依次乘10，如果不超过范围，则将数字放入结果中。否则先加一，如果达到边界（超过范围，或者结尾有0），则先除10，再继续往下排序。

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>(n);
        int num = 1;
        result.add(num);
        for (int i = 1; i < n; i++) {
            if (num * 10 <= n) {
                num *= 10;
                result.add(num);
                continue;
            }

            num++;
            while (num % 10 == 0) {
                num /= 10;
            }
            
            if (num > n) {
                num = num / 10 + 1;
            }
            
            while (num % 10 == 0) {
                num /= 10;
            }
            
            result.add(num);
        }
        
        return result;
    }
}