java创建了一个算法，将它们排列成可能的最大整数

Question

我正在努力解决Java中的这个编码问题。必须使用算法来解决这个问题。它应该给我一个可能的最大inter，它可以由数组中的数字组成：{10，7，76，415}。我尝试使用选择排序来解决它。到目前为止，我有下面的代码，但它给了我错误的输出。我的代码：

公共类最大数{ 公共静态最大整数（整数[]arr）{

    for (int i = 1; i < arr.length -1; i++) {
        for (int j = i +1; j < arr.length; j++) {
            String temp1 = Integer.toString(i) + Integer.toString(j);
            String temp2 = Integer.toString(j) + Integer.toString(i);
            
            if (Integer.parseInt(temp2) > Integer.parseInt(temp1)) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
            }
        }

    
    }
    
    String ansNum = "";
    for (int i = 0; i < arr.length; i++) {
        ansNum += Integer.toString(arr[i]);
        
    }
    
    return Integer.parseInt(ansNum);

}
public static void main(String[] args) {   
    int [] arr = {10, 7, 76, 415};
    int output = largestNumber(arr);
    System.out.println(output); //Print out the number
}

}

此代码的给定输出为：10415767 但正确的答案是：77641510

请给出您的反馈和想法

Answer 1

修复错误如下所示，它应该可以工作

for (int i = 0; i < arr.length; i++) { //correction here
        for (int j = i +1; j < arr.length; j++) {
                String temp1 = Integer.toString(arr[i]) + Integer.toString(arr[j]); //correction here
                String temp2 = Integer.toString(arr[j]) + Integer.toString(arr[i]); //correction here

为了编写一些优雅的代码，我会使用比较器，如下所示：

        String[] stringArr = new String[arr.length];
        for(int i = 0; i < arr.length; i++)
            stringArr[i] = String.valueOf(arr[i]);
    
        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                String s1 = str1 + str2;
                String s2 = str2 + str1;
                return s2.compareTo(s1);
            }
         };
        
        Arrays.sort(stringArr, comp);
    
        String ansNum = "";
        for(int i = 0; i < stringArr.length; i++) {
            ansNum += stringArr[i];
            
        }
        
        return Integer.parseInt(ansNum);

说到时间复杂度，代码中的两个for循环使这个解决方案O(n^2)成为O(nlog(n))，而使用sort则变成O(nlog(n))，其中n是输入数组中的元素数。因此，使用比较器不仅代码变得优雅，在这种情况下，代码也变得高效