贪心算法：最大数

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

最大数

题目地址： leetcode-cn.com/problems/la…

题目描述：

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意： 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例

输入： nums = [10,2]
输出： "210"
复制代码

输入： nums = [3,30,34,5,9]
输出： "9534330"
复制代码

题目分析

本题是一道贪心算法的题目，贪心算法是在局部求最优解。 面对本题时需要将数组中数值排序后组合生成一个最大的数值。

所以基本就是最大值放在最前面，然后把其他小一些的值放在后面

这里其实我思路一开始拐进胡同里了，说正确思路吧

1. 可能数组只有一个值，那么直接返回这个值的字符串即可（编译报错后发现的）

2. 数组数值全是0， 那么返回‘0’（编译报错后发现的）

3. 普通情况：

   这里可以对数组进行排序，因为我使用的是JavaScript语言，所以可以调用数组的sort方法，编写回调函数进行判断，在回调函数当中，可以直接通过(a + b)字符串与(b + a)字符串的整数值进行比较。 就比如[3, 34, 32]进行此规则排序时

   • 比较34和3， 就会变成343对比334，结果是34在3前
   • 比较32和34， 就会变成3234对比3432，结果是34在32前
   • 比较32和3， 就会变成323对比332，结果是3在32前

   最终得到结果数组[34, 3, 32]。将数组通过join组合起来，就是最终的结果字符串了

正确代码

var largestNumber = function(nums) {
    // 只有一个数直接返回
    if (nums.length == 1) {
        return nums[0] + ''
    }
    // 判断数组是否都是0
    let ifZero = 0;
    
    // 按照互加进行对比排序
    nums.sort((a, b)=>{
        if (a != 0 || b != 0) {
            ifZero = 1;
        }
        let aStr = a + '', bStr = b + '';
        return parseInt(bStr + aStr) - parseInt(aStr + bStr) ;
    })
    
    if (ifZero == 1) {
        return nums.join('');
    } else {
        return '0'
    }
};
复制代码

以下是我最开始的错误思路，

在最开始时，我先写了一个求高位的方法，然后每个数值一个高位一个高位对比过去，但是这样会出现没有位数的情况，那么就让上一个位数的值补上去，这里就错误了，编译遇到两次错误后就发现完全可以两个数值互加求出先后顺序

// 获取数字高位, 位数
function getHight(numStr, maxlen, len, addnum) {
    let needAdd = maxlen - len, res = numStr;
    for(let i = 0; i < needAdd; i++) {
        res += addnum;
    }
    return parseInt(res)
}
// 按照最高位排一次序
nums.sort((a, b)=>{
    let aStr = a + '', bStr = b + '', alen = aStr.length, blen = bStr.length;
    let maxLen = alen > blen ? alen : blen;
    return getHight(bStr, maxLen, blen, aStr.charAt(0)) - getHight(aStr, maxLen, alen, bStr.charAt(0)) ;
})
复制代码