每日一题:LeetCode-179. 最大数

作者：半亩房顶

2024-01-15
北京
本文字数：1086 字
阅读完需：约 4 分钟

刷题使我快乐，满脸开心.jpg

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

题目

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

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

示例 1：

输入：nums = [10,2]输出："210"

复制代码

示例 2：

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

复制代码

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 109

思路

这道问题关键就在于弄明白如何比较两个数字的大小，然后去排序就完事儿了

排序

首先是首位不同时，那么我们其实都知道，越把大的数往前放，那么最终结果越大，所以首位不同很容易比较
首位相同，这里其实分两种情况
第一种是在后续位置上能够发现不同，比如，"456" 和 "454"，那我们依然能够用不同位越大，最终越大的原则去判断
第二种是后续位置上没有能够发现不同，比如，"456" 和 "45"，"453" 和 "45"，这两种情况其实还会不同，需要分情况去讨论
但是其实我们有更便捷、心智负担更小的办法，那就是把两个数字用不同的顺序拼起来，这样一来，拼起来哪个数字更大，也就是说明哪个数字应该在前面！

特殊情况

最后要提一下就是小心"0"这个特殊情况。虽然我们最终要返回的是字符串，但其实我们要返回的是拼起来之后的数字的字符串表示，所以需要避免前缀 0 这类情况。

至此，也就没有太多可说的了，上代码。

代码

func largestNumber(nums []int) string {    numStrs := make([]string, 0, len(nums))    // 开始只是为了方便位比较，方便不补齐位数    // 后来看别人题解，发现还顺便规避了int溢出    for _, num := range nums {        numStrs = append(numStrs, strconv.Itoa(num))    }    sort.Slice(numStrs, func(i, j int) bool {        // 与其计算位数去补齐，不如直接拼起来看看哪个大        // 这样位数也肯定统一，不用考虑某一方溢出问题        strIJ := numStrs[i] + numStrs[j]        strJI := numStrs[j] + numStrs[i]        for k := 0; k < len(strJI); k++ {            if strIJ[k] > strJI[k] {                return true            } else if strIJ[k] < strJI[k] {                return false            }        }        return false    })
    // 兼容只有0的情况，最大的都是0了，后面指定都是0，不用拼了    // 其他情况都得拼起来    if numStrs[0] == "0" {        return "0"    }
    res := ""    for _, str := range numStrs {        res += str    }    return res}

复制代码

欢迎关注公众号交流更多题目~

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/591019ee8a5e27d46e664733c】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题:LeetCode-179. 最大数

题目

思路

排序

特殊情况

代码

半亩房顶

评论