问题描述:
给定一组非负整数 nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例一:
输入nums = [10,2]
输出:"210"
示例二:
输入nums = [3,30,34,5,9]
输出:"9534330"
问题解决:
这道题其实是一个自己指定排序规则的排序,而排序的过程就是贪心算法的体现,排序规则如下:
我们这里一数组里有两个数为例,分别是a和b
(1)ab > ba(这里的ab是将数据b添加到数据a的前面) ——> a在前,b在后
(2)ab = ba ——> 无所谓
(3)ab < ba——>b在前,a在后
其实这些比较就是贪心策略的体现。
那么这一个排序规则,为这么可以正确排序呢?
证明排序规则的排序是正确的:
证明方法:全序关系
什么事全序关系?
1.完全性:
设有两个元素a和b,一定要保证这两个元素是可以比大小的,
例如:a <= b 或者 a >= b
2.反对称性:
设有a,b两个元素,满足:
a <= b && a >= b ——> a = b
对应到本题中就是:
a在前 && b在后 ——>无所谓
3.传递性:
设有三个元素a,b,c,其满足:
a >= b && b>= c ——> a >= c
这个事最重要也是最难证明的一个。
接下来来使证明:
1.证明完全性:
2.证明反对称性:
3.证明传递性:
所以满足全序关系,说明我们规定的排序是正确的。
最后,题目要求输出的是字符串,所以有一个优化是可以在开始就将数组中的数字全部转化成字符
串,同时这样也有利于排序的比较,不用将整形数字拆分来比较,直接比较即可。
接下来就是代码的编写:
class Solution
{
public:
string largestNumber(vector<int>& nums)
{
//优化:将所有的数转换成字符串
vector<string> strs;
for(int x :nums)
{
strs.push_back(to_string(x));
}
//排序:
sort(strs.begin(),strs.end(),[](const string& s1,const string& s2)
{
return s1 + s2 > s2 + s1;
});
//提取结果;
string ret;
for(auto& s: strs)
{
ret += s;
}
if(ret[0] == '0')
{
return "0";
}
return ret;
}
};
这就是这到题的详细解析。