剑指 Offer 45. 把数组排成最小的数

class Solution { public: struct cmp{ bool operator()(string a, string b){return a+b < b+a ;} }cmp; string minNumber(vector<int>& nums) { vector<string> vec; for(auto num: nums) vec.push_back(to_string(num)); sort(vec.begin(),vec.end(),cmp); string result = ""; for(auto it=vec.begin();it!=vec.end();it++){ string str = *it; result += str; } return result; } };

证明见《剑指offer 第二版》P229-P230

书中有一步$$A_1{A}_2\cdots A_{y-1}{A}_y\cdots A_n<A_1{A}_2\cdots A_y{A}_{y-1}\cdots A_n$$ 让读者自己证明，下给出证明

因为$$A_{y-1}{A}_y<A_y{A}_{y-1}$$ 且两个字符串中$$A_1{A}_2\cdots A_{y-2}XX{A}_{y+1}\cdots A_n$$部分相同，且XX等长。所以$$A_1{A}_2\cdots A_{y-1}{A}_y\cdots A_n<A_1{A}_2\cdots A_y{A}_{y-1}\cdots A_n$$