LeetCode179:最大数

标签: # LeetCode  字符串  leetcode  动态规划  算法

题目

给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

通过次数37,345提交次数101,676

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

做法:转化为字符串,按照字典降序排序。

class Solution {
    public String largestNumber(int[] nums) {
        if(nums==null||nums.length==0)
            return "";
        String[]str = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(str,new Comparator<String>(){
            @Override
            public int compare(String s1,String s2){
               
                return (s2+s1).compareTo(s1+s2);
                /*
                假设(不是一般性),某一对整数 a 和 b ,我们的比较结果是 a 应该在 b 前面,这意味着a+b>b+a;
                如果排序结果是错的,说明存在一个 c, b 在 c 前面且 c 在 aa 的前面。这产生了矛盾,因为 a+ b> b+a和 b+c>c+b 意味着 a+c>c+a。
                换言之,我们的自定义比较方法保证了传递性,所以这样子排序是对的。
				一旦数组排好了序,最“重要”的数字会在最前面。
				有一个需要注意的情况是如果数组只包含 0 ,我们直接返回结果 00 即可。否则,我们用排好序的数组形成一个字符串并返回。
                */
            }
        });
        StringBuilder sb = new StringBuilder();
        for(String as:str){
            sb.append(as);
        }
        String result = sb.toString();
        if(result.charAt(0)=='0')
            result="0";
        return result;

    }
}

在这里插入图片描述

版权声明:本文为qq_44861675原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44861675/article/details/107834517