题解 | #字典序排列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型ArrayList
     */
    
    /**********************************************************************************/
    /*
    public ArrayList<Integer> orderArray (int n) {
        // write code here
        int[] nums = new int[n];
        for (int i = 1; i <= n; i++) {
            nums[i - 1] = i;
        }
        quickSort(nums, 0, n - 1);
        ArrayList<Integer> res = new ArrayList<>();
        for (int num : nums) {
            res.add(num);
        }
        return res;
    }
    
    public void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        int val = nums[end];
        while (p < r) {
            if (compare(nums[p], val) == -1) {
                int swap = nums[p];
                nums[p] = nums[l + 1];
                nums[l + 1] = swap;
                l++;
                p++;
            }
            else if (compare(nums[p], val) == 1) {
                int swap = nums[p];
                nums[p] = nums[r - 1];
                nums[r - 1] = swap;
                r--;
            }
            else {
                p++;
            }
        }
        quickSort(nums, start, l);
        quickSort(nums, r, end);
    }
    
    public int compare(int num1, int num2) {
        String str1 = String.valueOf(num1);
        String str2 = String.valueOf(num2);
        int len1 = str1.length();
        int len2 = str2.length();
        int p1 = 0;
        int p2 = 0;
        while (p1 < len1 && p2 < len2) {
            if (str1.charAt(p1) < str2.charAt(p2)) {
                return -1;
            }
            else if (str1.charAt(p1) > str2.charAt(p2)) {
                return 1;
            }
            else {
                p1++;
                p2++;
            }
        }
        if (len1 < len2) {
            return -1;
        }
        else if (len1 > len2) {
            return 1;
        }
        else {
            return 0;
        }
    }
    */
    
    /**********************************************************************************/
    public ArrayList<Integer> res = new ArrayList<>();

    public ArrayList<Integer> orderArray(int n) {
        if (n < 10) {
            for (int i = 1; i <= n; i++) {
                res.add(i);
            }
        }
        else {
            for (int i = 1; i < 10; i++) {
                process(i, n);
            }
        }
        return res;
    }

    public void process(int num, int n) {
        if (num > n) {
            return;
        }
        res.add(num);
        for (int i = 0; i < 10; i++) {
            process(num * 10 + i, n);
        }
    }
}