179最大数（贪心算法）分析+源码+证明
文章目录
- 题目
- 题目分析
- 算法原理
- 源码
- 证明
- 思考
题目
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
题目分析
首先这道题的意思是把数组内数组拼接在一起成为最大值。
算法原理
正常排序的本质：确定元素先后顺序：谁在前，谁在后。
本题的排序
根据正常排序，和本道题相似。
思考：1.贪心在哪体现：体现在比较，确定谁前谁后这个过程。
2.这个排序规则，为啥能排序：具有传递性。
eg：
3.优化:(1)把数转化为字符串，然后拼接字符串，比较字典序。
（2）字符串第一个数为0，结果一定为零
优化如下图：
源码
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;
}
};
证明
证明方法：数学知识（离散数学）
补充知识：全序关系（要满足：1.完全性2.反对称性3.传递关系）
要满足：
1.完全性(能比较大小)
2.反对称性
3.传递关系
证明本道题：
证明出这道题满足：1.完全性2.反对称性3.传递关系。过程如下图：
思考
以上就是179最大数（贪心算法）分析+源码+证明的全部内容了，非常详细。有啥问题可在评论区留言。喜欢博主的内容，可以一键三连。