题目描述

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

分析

最直接的方法是，将这几个数做全排列，得到所有可能的组合，然后对组合排序，选出最小的数。第二种方法是，设计一种排序方法，字符串m和n拼接，如果mn >nm,那么字符串n应该排在m的前面。

代码一

public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0) return "";
        String[] nums = new String[numbers.length];
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<numbers.length;i++)
            nums[i] = ""+numbers[i];
        Arrays.sort(nums,new Comparator<String> () {
            public int compare(String o1,String o2) {
                return (o1+o2).compareTo(o2+o1);
            }
        });
        for(int i=0;i<numbers.length;i++)
            sb.append(nums[i]);
        return sb.toString();
    }

代码二：全排列

ArrayList<String> res = new ArrayList<>();

    public String PrintMinNumber(int [] numbers) {
        permutation(numbers,0);
        String[] nums = new String[res.size()];
        for(int i=0;i<res.size();i++)
            nums[i] = res.get(i);
        Arrays.sort(nums);
        return nums[0];
    }
    
    private void permutation(int[] numbers,int pos) {
        if(pos >= numbers.length) {  
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<numbers.length;i++)
                sb.append(""+numbers[i]);
            res.add(sb.toString());
            return;
        }
        for(int i=pos;i<numbers.length;i++) {
            swap(numbers,pos,i);
            permutation(numbers,pos+1);
            swap(numbers,pos,i);
        }
    }

    private void swap(int[] numbers, int i,int j) {
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;
    }