题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路

1. 解法1

   使用全排列方式，将所有的可能排列出来，每次得到一个排列，记录其中的最小的一个值。

2. 解法2

   第一种解法需要求解所有的排列，时间复杂度高。我们可以使用一种排序算法，实现对数据排序。排序规则是，当两个数拼接在一起， 如 mn < nm，那么 m 就小于 n。

实现

1. 解法1

public class Solution {    public String PrintMinNumber(int [] numbers) {        if (numbers == null || numbers.length <= 0) return "";        return recursion(numbers, 0, "");    }    private String recursion(int[] numbers, int i, String s) {        if (i == numbers.length) return s;        String min = null;        for (int j = i; j < numbers.length; j++){            swap(numbers, i, j);            String now = recursion(numbers, i + 1, s+numbers[i]);            min = min == null ? now : (min.compareTo(now) < 0 ? min : now);            swap(numbers, i, j);        }        return min;    }    private void swap(int[] numbers, int i, int j) {        int tmp = numbers[i];        numbers[i] = numbers[j];        numbers[j] = tmp;    }}

1. 解法2

import java.util.Comparator;public class Solution {    public String PrintMinNumber(int [] numbers) {        if (numbers == null || numbers.length <= 0) return "";        sort(numbers, 0, numbers.length-1,new Comparator
    
     (){            @Override            public int compare(Integer o1, Integer o2) {                StringBuilder sb1 = new StringBuilder();                sb1.append(o1).append(o2);                StringBuilder sb2 = new StringBuilder();                sb2.append(o2).append(o1);                String s1 = sb1.toString();                String s2 = sb2.toString();                return s1.compareTo(s2);            }        });        StringBuilder sb = new StringBuilder();        for (int i = 0; i < numbers.length; i++){            sb.append(numbers[i]);        }        return sb.toString();    }    private void sort(int[] numbers, int start, int end, Comparator
     
       comparator) {        int p = partion(numbers, start, end, comparator);        if (start < p){            sort(numbers, start, p-1, comparator);        }        if (end > p && p != -1){            sort(numbers, p+1,end,comparator);        }    }    private int partion(int[] numbers, int start, int end, Comparator
      
        comparator) {        if (start > end) return -1;        int tmp = numbers[start];        while (start < end){            while (start < end && comparator.compare(numbers[end],tmp) >= 0) end--;            if (start < end)                numbers[start++] = numbers[end];            while (start < end && comparator.compare(numbers[start],tmp) < 0) start++;            if (start < end)                numbers[end--] = numbers[start];        }        numbers[start] = tmp;        return start;    }}