問(wèn)題描述：輸入一個(gè)正整數(shù)數(shù)組，將它們連接起來(lái)排成一個(gè)數(shù)，輸出能排出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{32,  321}，則輸出這兩個(gè)能排成的最小數(shù)字32132。請(qǐng)給出解決問(wèn)題的算法，并證明該算法。
      思路：先將整數(shù)數(shù)組轉(zhuǎn)為字符串?dāng)?shù)組，然后字符串?dāng)?shù)組進(jìn)行排序，最后依次輸出字符串?dāng)?shù)組即可。這里注意的是字符串的比較函數(shù)需要重新定義，不是比較a和b，而是比較ab與 ba。如果ab < ba，則a < b；如果ab > ba，則a > b；如果ab = ba，則a = b。比較函數(shù)的定義是本解決方案的關(guān)鍵。
      證明：為什么這樣排個(gè)序就可以了呢？簡(jiǎn)單證明一下。根據(jù)算法，如果a < b，那么a排在b前面，否則b排在a前面?？衫梅醋C法，假設(shè)排成的最小數(shù)字為xxxxxx，并且至少存在一對(duì)字符串滿足這個(gè)關(guān)系：a > b，但是在組成的數(shù)字中a排在b前面。根據(jù)a和b出現(xiàn)的位置，分三種情況考慮：
      （1）xxxxab，用ba代替ab可以得到xxxxba，這個(gè)數(shù)字是小于xxxxab，與假設(shè)矛盾。因此排成的最小數(shù)字中，不存在上述假設(shè)的關(guān)系。
      （2）abxxxx，用ba代替ab可以得到baxxxx，這個(gè)數(shù)字是小于abxxxx，與假設(shè)矛盾。因此排成的最小數(shù)字中，不存在上述假設(shè)的關(guān)系。
      （3）axxxxb，這一步證明麻煩了一點(diǎn)。可以將中間部分看成一個(gè)整體ayb，則有ay < ya，yb < by成立。將ay和by表示成10進(jìn)制數(shù)字形式，則有下述關(guān)系式，這里a，y，b的位數(shù)分別為n，m，k。
        關(guān)系1： ay < ya => a * 10^m + y < y * 10^n + a => a * 10^m - a < y * 10^n - y => a( 10^m - 1)/( 10^n - 1) < y
        關(guān)系2： yb < by => y * 10^k + b < b * 10^m + y => y * 10^k - y < b * 10^m - b => y < b( 10^m -1)/( 10^k -1)
        關(guān)系3： a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)  => a/( 10^n - 1)< b/( 10^k -1) => a*10^k - a < b * 10^n - b =>a*10^k + b < b * 10^n + a => a < b
       這與假設(shè)a > b矛盾。因此排成的最小數(shù)字中，不存在上述假設(shè)的關(guān)系。
       綜上所述，得出假設(shè)不成立，從而得出結(jié)論：對(duì)于排成的最小數(shù)字，不存在滿足下述關(guān)系的一對(duì)字符串：a > b，但是在組成的數(shù)字中a出現(xiàn)在b的前面。從而得出算法是正確的。
      參考代碼：

//重新定義比較函數(shù)對(duì)象 
struct compare 
{ 
 bool operator() (const string &src1, const string &src2) 
 { 
  string s1 = src1 + src2; 
  string s2 = src2 + src1; 
  return s1 < s2; //升序排列，如果改為s1 > s2則為逆序排列 
 } 
}; 
//函數(shù)功能 ： 把數(shù)組排成最小的數(shù) 
//函數(shù)參數(shù) ： pArray為數(shù)組,num為數(shù)組元素個(gè)數(shù) 
//返回值 ： 無(wú) 
void ComArrayMin(int *pArray, int num) 
{ 
 int i; 
 string *pStrArray = new string[num]; 
 
 for(i = 0; i < num; i++) //將數(shù)字轉(zhuǎn)換為字符串 
 {  
  stringstream stream; 
  stream<<pArray[i]; 
  stream>>pStrArray[i]; 
 } 
 
 sort(pStrArray, pStrArray + num, compare()); //字符串?dāng)?shù)組排序 
 
 for(i = 0; i < num; i++) //打印字符串?dāng)?shù)組 
  cout<<pStrArray[i]; 
 cout<<endl; 
 
 delete [] pStrArray; 
} 

最新評(píng)論