创建一个算法来排列它们以形成最大可能的整数

Question

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

public class最大数{ public static int largestNumber(int[] 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
}

}

此代码的给定输出is: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) 而使用 sort 它变成 O(nlog(n)) 其中n 是输入数组中的元素数。因此，使用比较器不仅代码变得优雅，在这种情况下它也变得高效。

Answer 2

public class largestNumber { 
  public static int largestNumber(int[] arr) {

    for (int i = 0; i < arr.length -1; i++) {
        for (int j = i +1; j < arr.length; j++) {
            String temp1 = Integer.toString(arr[i]) + Integer.toString(arr[j]);
            String temp2 = Integer.toString(arr[j]) + Integer.toString(arr[i]);//rectified
            
            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
    }
}

创建一个算法来排列它们以形成最大可能的整数

Create an algorithm that arranges them in order to form the largest possible integer

java

sorting

algorithm

selection-sort