題目描述：

給出一組非負(fù)整數(shù)，將這組整數(shù)拼接成一個(gè)數(shù)字，要求數(shù)字最大，用string返回這個(gè)最大的數(shù)字

For example, given?[3, 30, 34, 5, 9], the largest formed number is?9534330

?

---

?

題目分析：

對(duì)于數(shù)字 a，b到底哪個(gè)在前面組成的數(shù)字大一點(diǎn)呢，只要比較 ab 和 ba 這兩個(gè)字符串就可以了 ，如果ab>ba應(yīng)該將a放到前面，反之將a放到后面

這樣可以對(duì)多有整數(shù)按照上面的比較方法，按照從大到小排序；排序之后只要一個(gè)一個(gè)的拼接起來就可以了

?

問題：

在使用sort時(shí)碰到了點(diǎn)問題：

當(dāng)數(shù)組中的所有元素都相同時(shí)：

　　如果cmp函數(shù)定義成這種格式 if(a>=b)return true; 排序之后會(huì)出現(xiàn)奇怪的數(shù)字，或者一直跑不出來

　　但是如果cmp函數(shù)定義成這種格式 if(a>b)return true; 排序就不會(huì)出現(xiàn)問題了

對(duì)于上面的問題只有在數(shù)據(jù)量 >=17 時(shí)才出現(xiàn)（應(yīng)該在數(shù)據(jù)量小于17時(shí)采用的是插入排序）

?

之前沒注意排序過后一直會(huì)出問題，用自己的排序模板類通過了

后來發(fā)現(xiàn)去掉“=”就沒問題

原因至今不清楚。。。

?

---

?

代碼：

1 template<class T>class Qsort{ 2 private : 3 void copy(T &a,T &b){ 4 if(&a==&b)return ; 5 char *pa=(char *)&a; 6 char *pb=(char *)&b; 7 for(int i=0;i<sizeof(T);i++)*(pa+i)=*(pb+i); 8 } 9 10 void Swap(T & a,T & b){ 11 T buf; 12 copy(buf,a); 13 copy(a,b); 14 copy(b,buf); 15 } 16 public : 17 void qsort(T d[],int l,int r,bool (*cmp)(const T& a,const T& b)){ 18 if(l>=r)return ; 19 20 Swap(d[l],d[(l+r)>>1]); 21 int last=l; 22 23 for(int i=l+1;i<=r;i++) 24 if(!cmp(d[l],d[i])) 25 Swap(d[++last],d[i]); 26 Swap(d[l],d[last]); 27 28 qsort(d,l,last-1,cmp); 29 qsort(d,last+1,r,cmp); 30 } 31 }; 32 class Solution { 33 public: 34 static string itos(int n){ 35 string ret=""; 36 if(n==0)return "0"; 37 while(n){ 38 ret=(char)(n%10+'0')+ret; 39 n=n/10; 40 } 41 return ret; 42 } 43 44 static bool cmp(const int &a,const int &b){ 45 string s1=itos(a); 46 string s2=itos(b); 47 int i; 48 string merge1=s1+s2; 49 string merge2=s2+s1; 50 if(merge1.compare(merge2)>=0)return true; 51 return false; 52 } 53 54 string largestNumber(vector<int> &num) { 55 int a[num.size()]; 56 for(int i=0;i<num.size();i++)a[i]=num[i]; 57 Qsort<int> st; 58 st.qsort(a,0,num.size()-1,cmp); 59 if(a[0]==0)return "0"; 60 string ret=""; 61 for(int i=0;i<num.size();i++) 62 ret=ret+itos(a[i]); 63 return ret; 64 } 65 };

?

1 static inline string itos(int n){ 2 string ret=""; 3 if(n==0)return "0"; 4 while(n){ 5 ret=(char)(n%10+'0')+ret; 6 n=n/10; 7 } 8 return ret; 9 } 10 11 static inline int cmp(const string &a,const string &b){ 12 if((a+b).compare(b+a)>0)return 1; 13 return 0; 14 } 15 16 string largestNumber(vector<int> &num) { 17 string st[num.size()]; 18 for(int i=0;i<num.size();i++)st[i]=itos(num[i]); 19 20 sort(st,st+num.size(),cmp); 21 22 if(st[0][0]=='0')return "0"; 23 24 string ret=""; 25 for(int i=0;i<num.size();i++) 26 ret=ret+st[i]; 27 return ret; 28 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/li-xingtao/p/4223925.html

總結(jié)

以上是生活随笔為你收集整理的Largest Number 179的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。