【劍指Offer學習】【面試題33：把數組排成最小的數】

題目：輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個。

例子說明：

例如輸入數組{3， 32, 321}，則掃描輸出這3 個數字能排成的最小數字321323。

解題思路：

第一種：直覺解法

先求出這個數組中所有數字的全排列，然後把每個排列拼起來，最後求出拼起來的數字的最大值。

第二種：排序解法

找到一個排序規則，數組根據這個規則排序之後能排成一個最小的數字。要确定排序規則，就要比較兩個數字，也就是給出兩個數字m 和n，我們需要确定一個規則判斷m 和n 哪個應該排在前面，而不是僅僅比較這兩個數字的值哪個更大。

根據題目的要求，兩個數字m 和n能拼接成數字m和m。如果mn < nm，那麼我們應該列印出m，也就是m 應該排在n 的前面，我們定義此時m 小于n：反之，如果nm < mn，我們定義n小于m。如果mn=nm,m 等于n。在下文中，符号“<”、“>”及“＝”表示正常意義的數值的大小關系，而文字“大于”、“小于”、“等于”表示我們新定義的大小關系。

接下來考慮怎麼去拼接數字，即給出數字m和n，怎麼得到數字m和m 并比較它們的大小。亘接用數值去計算不難辦到，但需要考慮到一個潛在的問題就是m 和n 都在int 能表達的範圍内，但把它們拼起來的數字m 和m 用int 表示就有可能溢出了，是以這還是一個隐形的大數問題。

一個非常直覺的解決大數問題的方法就是把數字轉換成字元串。另外，由于把數字m 和n 拼接起來得到m 和m，它們的位數肯定是相同的，是以比較它們的大小隻需要按照字元串大小的比較規則就可以了。

本題采用第二種方法實作

代碼實作：

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) >= ) {
                    end--;
                }

                array[start] = array[end];

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

            }

            array[start] = pivot;

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

    /**
     * 題目：輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，
     * 列印能拼接出的所有數字中最小的一個。
     * @param array 輸入的數組
     * @return 輸出結果
     */
    public static String printMinNumber(String[] array) {

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

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

        StringBuilder builder = new StringBuilder();
        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));
    }
}
           

運作結果：