【Leetcode刷题记录】179. 最大数--贪心法自定义排序策略

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

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

第一反应是数组降序排，大数在高位小数在低位，但显然不是这样的，比如说nums=[10,9]，910显然比109大。比较靠谱的思路是让高位的数字尽可能的大，比如说nums=[9,5,30]，将每一个元素转成字符串排序，得到nums_str=["9","5","30"]，这个思路看起来很好，但是题目给的这个用例nums = [3,30,34,5,9]，排序后得到nums_str=["9","5","34","30","3"]，这个结果是9534303但是9534330是更大的结果，"30"+"3"的结果不如"3"+"30"的结果好 ，因此不能简单的进行排序。当两个字符串a和b在拼接的时候，如果满足a+b>b+a那么就认为a要排在b的前面，反之a要排在b的后面。

那么这个排序策略是否正确，还需要证明反身性和传递性。

反身性是指任何元素与自身比较时都应该是相等的，对与任意一个数字x,转换成字符串后x+x=x+x，这里是显然成立的。

传递性这里是指如果a比b“更优”，而b又比c“更优”，那么a也应该比c“更优”，也就是$对于任意非负数字（已转成字符串）a,b,c，如果a+b>b+a,b+c>c+b,那么有a+c>c+a$

传递性的证明如下：
$$\begin{gathered} 如果a,b,c的位数分别是x,y,z,那么a+b\iff a\ast 10^y+b,b+a\iff b\ast 10^x+a \\ a+b>b+a\iff a\ast 10^y+b>b\ast 10^x+a,即\frac{a}{10^x-1}>\frac{b}{10^y-1} \\ 同理可以得到\frac{b}{10^y-b}>\frac{c}{10^z-1},因此有\frac{a}{10^x-1}>\frac{c}{10^z-1}，这个式子变形一下得a\ast 10^z+c>c\ast 10^x+a \\ 也就是a+c>c+a，传递性得证。 \end{gathered}$$
因此这个排序策略是正确的。

代码

string largestNumber(vector<int>& nums) {vector<string> str_num;for (int i = 0; i < nums.size(); i++)str_num.push_back(to_string(nums[i]));sort(str_num.begin(), str_num.end(), [&](string& str_a, string& str_b) {return str_a + str_b > str_b + str_a;});string ret;for(auto& str:str_num){if(!(str=="0"&&ret[0]=='0')) ret+=str;}return ret;
}