当前位置：首页 > article >正文

Java贪心算法每日一题——179.最大数

article 2024/11/18 3:24:39

题目链接：. - 力扣（LeetCode）

一、解题思想

将数组中的数重新排列，组成一个最大的整数。这题无法单纯的从对数字大小的比较得出排列结果。

所以，我们不能仅通过数字大小来排序，而应该是以组合完的大小进行排序。排序能顺利进行有三个重要条件：

1、排序的完全性

排序的完全性即，排序是能够比较大小的。要么是 A>=B，要么是B>=A。

2、排序的反对称性

反对称性即需要证明 AB <= BA 且 AB >= BA，则 AB = BA。

3、排序的传递性

二、题解代码

class Solution {
    public String largestNumber(int[] nums) {
        //优化：把所有数字转换为字符串，通过比较字典序来判断大小
        int n = nums.length;
        String[] strs = new String[n];
        for(int i = 0;i < n;i++) {
            //转换为字符串
            strs[i] = ""+nums[i];
        }

        //排序
        Arrays.sort(strs,(a,b) -> {
            return (b+a).compareTo(a+b);
        });

        //提取结果，使用StringBuffer来拼接
        StringBuffer ret = new StringBuffer();
        for(String s:strs) {
            ret.append(s);
        }

        //如果首位为0，说明这个字符串都是0
        if(ret.charAt(0) == '0') {
            return "0";
        }
        return ret.toString();
    }
}

查看全文

http://www.kler.cn/a/301746.html