题目
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
示例 2:
输入: [3,30,34,5,9] 输出: "3033459"
解题
方法一：使用内置排序
class Solution { public: static bool cmp(string& a,string& b){ return a+b<b+a; } string minNumber(vector<int>& nums) { //将元素转为string vector<string> strs; for(int num:nums) strs.push_back(to_string(num)); //排序 sort(strs.begin(),strs.end(),cmp); //输出结果 string res; for(string str:strs) res+=str; return res; } };
方法二：快排
class Solution { public: string minNumber(vector<int>& nums) { vector<string> strs; for(int num:nums) strs.push_back(to_string(num)); quickSort(strs,0,strs.size()-1); string res; for(string str:strs){ res+=str; } return res; } void quickSort(vector<string>& strs,int l,int r){ if(l>=r) return; int i=l,j=r; while(i<j){ while(i<j&&strs[j]+strs[l]>=strs[l]+strs[j]) j--; while(i<j&&strs[i]+strs[l]<=strs[l]+strs[i]) i++; swap(strs[i],strs[j]); } swap(strs[l],strs[i]); quickSort(strs,l,i-1); quickSort(strs,i+1,r); } };
