输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

思路：1.先求所有的组合，然后将list按字典序排列 2.快排

组合

public class Solution {
    int[] nums;
    List<String> list = new ArrayList<>();
    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length == 0) return "";
        nums = numbers;
        permutation(0);
        Collections.sort(list);
        return list.get(0);
    }
    
    private void permutation(int index) {
        if (index == nums.length - 1) {
            list.add(toString(nums));
            return;
        }
        for (int i = index; i < nums.length; i++) {
            swap(i, index);
            permutation(index + 1);
            swap(i, index);
        }
    }
    
    private void swap(int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private String toString(int[] nums) {
        String sb = "";
        for (int i : nums) {
            sb = sb + i;
        }
        return sb;
    }
}

快排

public class Solution {
    int[] nums;
    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length == 0) return "";
        this.nums = numbers;
        sort(0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i : nums) {
            sb.append(i);
        }
        return sb.toString();
    }
    
    private void sort(int i, int j) {
        if (i >= j) return;
        int m = partition(i, j);
        sort(i, m - 1);
        sort(m + 1, i);
    }

    private int partition(int lo, int hi) {
        int i = lo, j = hi + 1;
        int v = nums[lo];
        while(true) {
            while(less(nums[++i], v)) if (i == hi) break;
            while(less(v, nums[--j])) if (j == lo) break;
            if (i >= j) break;
            swap(i, j);
        }
        // 当跳出while的时候，i >= j ，所以 j 是较小的那一个
        swap(lo, j);
        return j;
    }
    
    private boolean less(int i, int j) {
        return ("" + i + j).compareTo("" + j + i) < 0;
    }
    private void swap(int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

直接使用 Array.sort() 进行排序

注意使用 Array.sort()如果使用 Comparator 不能对 int[] 排序,需要先转化成Integer[]

public class Solution {
    public String printMinNumber(int [] numbers) {
        if (numbers == null || numbers.length == 0) return "";
        String[] str = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(str, (n1, n2) -> (n1 + n2).compareTo(n2 + n1));
        StringBuilder sb = new StringBuilder();
        for (String i : str) {
            sb.append(i);
        }
        return sb.toString();
    }
}