leetcode-179-最大数-java

    技术2023-05-30  19

    题目及测试

    package pid179; /*最大数 给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。 示例 1: 输入: [10,2] 输出: 210 示例 2: 输入: [3,30,34,5,9] 输出: 9534330 说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。 */ public class main { public static void main(String[] args) { int[][] testTable = {{999999998,999999997,999999999},{3,30,34,5,9}}; for (int[] ito : testTable) { test(ito); } } private static void test(int[] ito) { Solution solution = new Solution(); String rtn; long begin = System.currentTimeMillis(); for (int i = 0; i < ito.length; i++) { System.out.print(ito[i]+" "); }//开始时打印数组 System.out.println(); rtn = solution.largestNumber(ito);//执行程序 long end = System.currentTimeMillis(); System.out.println("rtn=" + rtn); System.out.println("耗时:" + (end - begin) + "ms"); System.out.println("-------------------"); } }

    解法1(成功,5ms,极快)

    先对数组进行排序

    a+b>b+a,则a大,如3 12 3*100+12 12*10+3,312>123,则3>123,

    然后按这种排序方法,从大到小一次放到最前面

    package pid179; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.List; public class Solution { public String largestNumber(int[] nums) { List<Integer> list = new ArrayList<Integer>(nums.length); for(int num:nums){ list.add(num); } Collections.sort(list, new Comparator<Integer>() { public int compare(Integer a, Integer b) { return whoFirstWhoBig(a,b); } }); StringBuilder result = new StringBuilder(); boolean allZero = true; for(int i=list.size()-1;i>=0;i--){ int num = list.get(i); result.append(num); if(num !=0){ allZero = false; } } if(allZero){ return "0"; } return result.toString(); } // length为10 private int[] num10s = new int[]{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; /** a与b,a+b>b+a,则a大 * @param a * @param b * @return */ private int whoFirstWhoBig(Integer a, Integer b) { if(a == 0){ return -1; } if(b == 0){ return 1; } // 3 12 3*100+12 12*10+3 int indexA = 0; int indexB = 0; for(int i=0;i<10;i++){ if(a >= num10s[i]){ indexA = i; }else{ break; } } for(int i=0;i<10;i++){ if(b >= num10s[i]){ indexB = i; }else{ break; } } long aB = (long)a * num10s[indexB] * 10 +b; long bA = (long)b * num10s[indexA] * 10 +a; if(aB > bA){ return 1; }else{ return -1; } } }

    解法2(别人的)

    为了构建最大数字,我们希望越高位的数字越大越好。

    首先,我们将每个整数变成字符串。然后进行排序。

    如果仅按降序排序,有相同的开头数字的时候会出现问题。比方说,样例 2 按降序排序得到的数字是 9534330 ,然而交换 3 和 30 的位置可以得到正确答案 9534330 。因此,每一对数在排序的比较过程中,我们比较两种连接顺序哪一种更好。我们可以证明这样的做法是正确的:

    假设(不是一般性),某一对整数 a 和 b ,我们的比较结果是 a 应该在 b 前面,这意味着 ab>ba 。如果排序结果是错的,说明存在一个 c , b 在 c 前面且 c 在 a 的前面。这产生了矛盾,因为 ab>ba 和 bc>cb 意味着 ac>ca 。换言之,我们的自定义比较方法保证了传递性,所以这样子排序是对的。

    一旦数组排好了序,最“重要”的数字会在最前面。有一个需要注意的情况是如果数组只包含 0 ,我们直接返回结果 0 即可。否则,我们用排好序的数组形成一个字符串并返回。

    class Solution { private class LargerNumberComparator implements Comparator<String> { @Override public int compare(String a, String b) { String order1 = a + b; String order2 = b + a; return order2.compareTo(order1); } } public String largestNumber(int[] nums) { // Get input integers as strings. String[] asStrs = new String[nums.length]; for (int i = 0; i < nums.length; i++) { asStrs[i] = String.valueOf(nums[i]); } // Sort strings according to custom comparator. Arrays.sort(asStrs, new LargerNumberComparator()); // If, after being sorted, the largest number is `0`, the entire number // is zero. if (asStrs[0].equals("0")) { return "0"; } // Build largest number from sorted array. String largestNumberStr = new String(); for (String numAsStr : asStrs) { largestNumberStr += numAsStr; } return largestNumberStr; } }

     

     

    Processed: 0.022, SQL: 8