LeetCode-179:數組自動排序工具Arrays.sort()，比較器Comparator的正确打開方式

題目描述：給定一組非負整數，重新排列它們的順序使之組成一個最大的整數

執行個體一：輸入: [10,2] 輸出: 210

執行個體二：輸入: [3,30,34,5,9] 輸出: 9534330

在這道題上花費的時間比較多，主要是考慮問題的總是不夠全面，送出了很多次都沒有通過。

一開始的思路是，讓每兩個數進行比較，當然肯定不是直接比較，比如說5和21比較，後者大，但是需要将5排在前面。是以很容易想到比較第一位。那麼如果第一位相同，第二位不同；前兩位相同第三位不同呢，等等等等。是以我想到的是先将兩個數字補充為同樣位數的再進行比較。比如5和21，我先将5換成50，再與21進行比較。很快，一頓操作猛如虎，完成了測試代碼，送出後發現并沒有通過。測試代碼為[12,121]，按照我的邏輯，進行比較的數為120和121，由于121大，是以将121放在前面，組合出來的數為12112，顯然，這個數肯定比12121小。瞬間有種被KO的感覺。

接着，調整一下思路，幹脆直接将兩個數直接拼接了再進行比較，比如A和B進行比較，先拼接成AB和BA，再将AB和BA進行大小比較。由于數字溢出最大值，是以肯定是将拼接後的字元串轉換成char數組，然後再用每位上的char進行大小比較。

執行個體代碼如下：

/**
 * 給定一組非負整數，重新排列它們的順序使之組成一個最大的整數。
 */
public class LeeCode179 {
    public String largestNumber(int[] nums) {
        String largestNumberString = "";
        for (int i = 0, len = nums.length; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (numComp(nums[i], nums[j])) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        //防止[0,0]
        if(nums[0]==0){
            return "0";
        }
        for (int num : nums) {
            largestNumberString = largestNumberString + num + "";
        }
        return largestNumberString;
    }

    /**
     * 将兩個數字補齊為同樣位數後再比較大小
     * @param num1
     * @param num2
     * @return
     */
    private boolean numComp(int num1, int num2) {
        boolean changeOrNot = false;
        //當需要調換兩個元素順序時，傳回true
        String str1 = Integer.toString(num1)+Integer.toString(num2);
        String str2 = Integer.toString(num2)+Integer.toString(num1);
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        //比較兩個數組對應位大小
        for(int i=0,len=str1.length();i<len;i++){
            if(chars1[i]<chars2[i]){
                return true;
            }else if(chars1[i]>chars2[i]){
                return false;
            }
        }
        return changeOrNot;
    }

}
           

建議根據思路再手動編輯代碼，因為自己也在調試過程中遇到了很多考慮不全面，或者思維局限的地方。比如針對測試資料[0,0],如果在按照之前的邏輯操作下來，傳回的字元串結果就是 00 ，不符合要求，于是在輸出前可以加上一個對首位的判斷。

到了這裡，本該漏出一絲惬意的笑容，可惜，執行時間和消耗記憶體方面雙雙沒有什麼優勢，于是瞻仰了一下官方的示例代碼。官方的思路更加簡單清晰一些，先是将int類型的數組一次性轉換為String類型的數組，然後使用自定義的數組排序工具進行自動排序，然後再按順序将排序後的String通過字元串拼接，列印出結果。這種方法确實高效很多，特别是資料更大的時候。同時，排序之前的一些預處理，或者說是特殊情況特殊處理，也能有效減少一些無必要流程的執行判斷。

官方執行個體代碼如下：

public class LeeCode179Standard {
    public String largestNumber(int[] num) {
        if (num.length == 0) {
            return "";
        }
        if (num.length == 1) {
            return Integer.toString(num[0]);
        }
        String[] str = new String[num.length];
        for (int i = 0; i < num.length; i++) {
            str[i] = Integer.toString(num[i]);
        }
        Arrays.sort(str, new StringComparator());
        StringBuilder sb = new StringBuilder("");
        for (int i = num.length - 1; i >= 0; i--) {
            sb.append(str[i]);
        }
        if (sb.charAt(0) == '0') {
            return "0";
        }
        return sb.toString();
    }
    class StringComparator implements Comparator<String> {
        public int compare(String s1, String s2) {
            if (s1.length() == 0 && s2.length() == 0) {
                return 0;
            }
            if (s2.length() == 0) {
                return 1;
            }
            if (s1.length() == 0) {
                return -1;
            }
            for (int i = 0; i < s1.length() && i < s2.length(); i++) {
                if (s1.charAt(i) > s2.charAt(i)) {
                    return 1;
                } else if (s1.charAt(i) < s2.charAt(i)) {
                    return -1;
                }
            }
            if (s1.length() == s2.length()) {
                return 0;
            }
            if (s1.length() > s2.length()) {
                if (s1.charAt(0) < s1.charAt(s2.length())) {
                    return 1;
                } else if (s1.charAt(0) > s1.charAt(s2.length())) {
                    return -1;
                } else {
                    return compare(s1.substring(s2.length()), s2);
                }
            } else {
                if (s2.charAt(0) < s2.charAt(s1.length())) {
                    return -1;
                } else if (s2.charAt(0) > s2.charAt(s1.length())) {
                    return 1;
                } else {
                    return compare(s1, s2.substring(s1.length()));
                }
            }
        }
    }
}