【LeetCode】Largest Number解題報告

【テーマ】
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given  [3, 30, 34, 5, 9] , the largest formed number is  9534330 .
Note: The result may be very large, so you need to return a string instead of an integer.
Credits: Special thanks to @ts for adding this problem and creating all test cases. 【題意】
配列が与えられ、これらの数がつながって大きな数を構成し、最大数を構成することができます.
[3,30,34,5,9]のように構成できる最大数は9534330である.
構成の数が非常に大きい可能性があるため、文字列で返します.
【解法】
//煩雑な分析を聞きたくない授業はスキップして直接コードを見て、コードの中に注釈があります
肝心なのは、各数の最終結果における前後位置を決定することであり、比較的直観的には、例の9が5、4、3の前にあるほど前に大きい.
例の34は30より前であるべきである.
難点は桁数が異なる場合、前後関係はどのように確定しますか?例3のように、30と34の前、後、それとも中間に置くべきですか.
結局3は34と30の間に置かれていましたが、なぜでしょうか.これは10位の4が個位の3より大きいため、34は3より前で、10位の0は個数の3より小さいので、30は3より後です.
このように法則を見つけることができるように、1234が12を含むような関係のある数に対して、1234が12より多い部分34が12より大きいか小さいかを見るだけです.
このような方法で、前後の順序も判断できるようだ.ただ、565656や56など、考慮すべき状況は複雑すぎます.
//正解:
考えを変えることができて、2つの数の最終結果の中の前後の位置を比較したいならば、直接異なる組み合わせの結果の大きさを比較しませんか?
例を挙げると、3と34の前後位置を比較するには、334と343の大きさを比較することができ、343は334より大きいので、34は前にあるべきである.
これにより,2つの数を比較する方法があり,配列全体をソートすることができる.それから順番に並んだ数をつなぎ合わせるといいです.
【Javaコード】

public class Solution {
    public String largestNumber(int[] num) {
		int n = num.length;
        if (n < 1) return "";
        
        //           
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = String.valueOf(num[i]);
        }
        
        //             
        Arrays.sort(strs, new Cmp());
        
        //           
        String ans = "";
        for (int i = n - 1; i >= 0; i--) {
        	ans = ans.concat(strs[i]);
        }
        
        //       0，   [0, 0]
        int i = 0;
        while (i < n && ans.charAt(i) == '0') {
            i++;
        }
        if (i == n) return "0";
        
        return ans.substring(i);
    }
}

//       ：  [a  b  ]       [b  a  ]     ，  a>b。
class Cmp implements Comparator<String>{
	@Override
	public int compare(String a, String b) {
		String ab = a.concat(b);
		String ba = b.concat(a);
		return Integer.parseInt(ab) - Integer.parseInt(ba);
	}
}