【每日一题】179. 最大数

大数"/>

【每日一题】179. 最大数

文章目录

• • 题目
  • 解题思路
  • 代码（C++）
  • 总结

题目

题目链接：179. 最大数

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10⁹

解题思路

这题就是字典序排序，但是有一个注意的地方是：3 是大于 30 的。由于这个不一样的地方所以需要对排序进行一些改变。

👉更改排序函数

无论是对数字还是字符串 sort 函数都是可以排序的，数字是默认从小到大，字符串是默认从小到大按字典序排序的。所以这题可以用 sort 函数排序，但是需要对函数的排序方式更改。因为默认的是 3 < 30 ，所以要改为大于才行。

那么如何更改呢？如果让排序方式遇到像 3 和 30 的情况时返回相反的情况就可以了，但是这就需要函数判断需要比较的两个字符串是否是这种情况，所以就有了：return s1 + s2 > s2 + s1。这种方法可以很好的解决这个问题。无论是对于这种情况还是其他情况，都会返回正确的排序。

对于字典序排序，如果是比赛当然建议直接调用函数，但如果是面试，调用函数有时可能不太好，尤其是题目明确考你字典序排序的时候。所以讲一下字典序排序的方法吧。字典序是按照首字母的大小排序，如果首字母相等那么就依次比较后面的字母。

所以在比较两个字符串时，需要记录两字符串的长度，然后再依次比较字符串的字母，如果比较到某一个字母出现不相等时，那就直接返回大小。如果某个字符串是另一个的前缀，那么长的那个字符串大于短的。对了，可以用前缀和来比较，不过需要先把字符串存储起来。

代码（C++）

class Solution {
public:static bool cmp(string s1, string s2) {return s1 + s2 > s2 + s1;}string largestNumber(vector<int>& nums) {vector<string> str;for (int i = 0; i < nums.size(); ++ i) {str.push_back(to_string(nums[i]));}sort(str.begin(), str.end(), cmp);string s;if (str[0] == "0")return "0";for (int i = 0; i < str.size(); ++ i)s += str[i];return s;}
};

总结

本题总的来说不算难，只是在更改排序方式上确实难想到，但是写过一次记住了就不难了。对于字典序其实实现也不难，只是遍历字符串比较大小，但如果时间复杂度有要求的话，可以考虑用前缀和。