把数组排成最小的数

题目

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

思路

遇到这个题，全排列当然可以做，但是时间复杂度为O(n!)。在这里我们自己定义一个规则，对拼接后的字符串进行比较。

排序规则如下：

  • 若ab > ba 则 a 大于 b，
  • 若ab < ba 则 a 小于 b，
  • 若ab = ba 则 a 等于 b；

根据上述规则，我们需要先将数字转换成字符串再进行比较，因为需要串起来进行比较。比较完之后，按顺序输出即可。

代码一

public class Test1 {
    public static void main(String[] args) {
        int [] numbers = {0,0};
        System.out.println(PrintMinNumber(numbers));
    }
    public static String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0)
        {
            return "";
        }
        int len = numbers.length;
        String[] str = new String[len];
        StringBuffer sb = new StringBuffer();
        //将数字型的放在字符串数组中。
        for (int i = 0; i < len; i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        //根据定义的规则重新对str进行升序排序
        Arrays.sort(str, new Comparator<String>() {

            @Override
            public int compare(String s1, String s2) {
                // TODO Auto-generated method stub
                String c1 = s1 + s2;
                String c2 = s2 + s1;

                return c1.compareTo(c2);
            }

        });
        //根据规则排好序，将结果依次放入stringbuffer中就行了
        for (int i = 0; i < len; i++) {
            sb.append(str[i]);
        }
        String strs = String.valueOf(sb);
        if(strs.length() > 1)
        {
            while (strs.charAt(0) == '0')
            {
                if(strs.length() == 1){
                    break;
                }
                strs = strs.substring(1);
            }
        }

        return strs.toString();
    }

代码二   还没看懂

if(numbers == null || numbers.length == 0)
        return "";
        List<String> list = new ArrayList<>();
        Arrays.stream(numbers).forEach(e -> list.add(String.valueOf(e)));
        System.out.println(list);
        list.sort((o1,o2)->(o2+o1).compareTo(o1+o2));
        System.out.println(list);
        StringBuilder res = new StringBuilder();
        list.stream().forEach(s -> res.append(s));
        System.out.println(res);
        if(res.toString().indexOf('0')==0) {
            return "0";
        }
        return res.toString();
    }

代码三 还没看懂

public class Test33 {

    /**
     * 自定义的排序比较器，实现算法说明的排序原理
     */
    private static class MComparator implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {

            if (o1 == null || o2 == null) {
                throw new IllegalArgumentException("Arg should not be null");
            }

            String s1 = o1 + o2;
            String s2 = o2 + o1;
            return s1.compareTo(s2);
        }
    }

    /**
     * 快速排序算法
     *
     * @param array      待排序数组
     * @param start      要排序的起始位置
     * @param end        要排序的结束位置
     * @param comparator 自定义的比较器
     */
    private static void quickSort(String[] array, int start, int end, Comparator<String> comparator) {

        if (start < end) {
            String pivot = array[start];
            int left = start;
            int right = end;
            while (start < end) {
                while (start < end && comparator.compare(array[end], pivot) >= 0) {
                    end--;
                }

                array[start] = array[end];

                while (start < end && comparator.compare(array[start], pivot) <= 0) {
                    start++;
                }
                array[end] = array[start];

            }

            array[start] = pivot;

            quickSort(array, left, start - 1, comparator);
            quickSort(array, start + 1, end, comparator);
        }
    }

    /**
     * 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
     * 打印能拼接出的所有数字中最小的一个。
     * @param array 输入的数组
     * @return 输出结果
     */
    public static String printMinNumber(String[] array) {

        if (array == null || array.length < 1) {
            throw new IllegalArgumentException("Array must contain value");
        }

        MComparator comparator = new MComparator();
        quickSort(array, 0, array.length - 1, comparator);

        StringBuilder builder = new StringBuilder(256);
        for (String s : array) {
            builder.append(s);
        }

        return builder.toString();
    }

    public static void main(String[] args) {

        String[] data = {"3", "5", "1", "4", "2"};
        System.out.println(printMinNumber(data));

        String[] data2 = {"3", "32", "321"};
        System.out.println(printMinNumber(data2));

        String[] data3 = {"3", "323", "32123"};
        System.out.println(printMinNumber(data3));

        String[] data4 = {"1", "11", "111"};
        System.out.println(printMinNumber(data4));

        String[] data5 = {"321"};
        System.out.println(printMinNumber(data5));
    }
}