时间戳

首页 > 解决方案 > 创建一个算法来排列它们以形成最大可能的整数

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

问题描述

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

公共类最大数字{公共静态int最大数字（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
}

}

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

请提供您的反馈和想法。

标签： javaalgorithmsortingselection-sort

解决方案

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

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))wheren是输入数组中元素的数量。因此，使用比较器不仅代码变得优雅，在这种情况下它也变得高效。

推荐阅读