面試題33 把數組排成最小的數

問題描述：輸入一個正整數數組，将它們連接配接起來排成一個數，輸出能排出的所有數字中最小的一個。例如輸入數組{32,  321}，則輸出這兩個能排成的最小數字32132。請給出解決問題的算法，并證明該算法。

      思路：先将整數數組轉為字元串數組，然後字元串數組進行排序，最後依次輸出字元串數組即可。這裡注意的是字元串的比較函數需要重新定義，不是比較a和b，而是比較ab與 ba。如果ab < ba，則a < b；如果ab > ba，則a > b；如果ab = ba，則a = b。比較函數的定義是本解決方案的關鍵。這道題其實就是希望我們能找到一個排序規則，根據這個規則排出來的數組能排成一個最小的數字。

      證明：為什麼這樣排個序就可以了呢？簡單證明一下。根據算法，如果a < b，那麼a排在b前面，否則b排在a前面。可利用反證法，假設排成的最小數字為xxxxxx，并且至少存在一對字元串滿足這個關系：a > b，但是在組成的數字中a排在b前面。根據a和b出現的位置，分三種情況考慮：

      （1）xxxxab，用ba代替ab可以得到xxxxba，這個數字是小于xxxxab，與假設沖突。是以排成的最小數字中，不存在上述假設的關系。

      （2）abxxxx，用ba代替ab可以得到baxxxx，這個數字是小于abxxxx，與假設沖突。是以排成的最小數字中，不存在上述假設的關系。

      （3）axxxxb，這一步證明麻煩了一點。可以将中間部分看成一個整體ayb，則有ay < ya，yb < by成立。将ay和by表示成10進制數字形式，則有下述關系式，這裡a，y，b的位數分别為n，m，k。

        關系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

        關系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) 

        關系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

       這與假設a > b沖突。是以排成的最小數字中，不存在上述假設的關系。

       綜上所述，得出假設不成立，進而得出結論：對于排成的最小數字，不存在滿足下述關系的一對字元串：a > b，但是在組成的數字中a出現在b的前面。進而得出算法是正确的。

代碼一：利用指針。

[html]  view plain copy

1. #include <iostream>  
2. #include <string.h>  
3. using namespace std;  
4. const int g_MaxNumberLength=10;  
5. char* g_StrCombine1=new char[g_MaxNumberLength*2+1];  
6. char* g_StrCombine2=new char[g_MaxNumberLength*2+1];  
7. int compare(const void* strNumber1, const void* strNumber2)  
8. {  
9.     strcpy(g_StrCombine1, *(const char**)strNumber1);  
10.     strcat(g_StrCombine1, *(const char**)strNumber2);  
11.     strcpy(g_StrCombine2, *(const char**)strNumber2);  
12.     strcat(g_StrCombine2, *(const char**)strNumber1);  
13.     return strcmp(g_StrCombine1, g_StrCombine2);  
14. }  
15. void PrintMinNumber(int *numbers, int length)  
16. {  
17.     if(numbers==NULL || length<=0)  
18.         return;  
19.     char** strNumbers=(char**)(new int[length]);  
20.     for(int i=0; i<length; i++)  
21.     {  
22.         strNumbers[i]=new char[g_MaxNumberLength+1];  
23.         sprintf(strNumbers[i], "%d", numbers[i]);  
24.     }  
25.     qsort(strNumbers, length, sizeof(char*), compare);  
26.     for(i=0; i<length; i++)  
27.         cout<<strNumbers[i];  
28.     cout<<endl;  
29.     for(i=0; i<length; i++)  
30.         delete[] strNumbers[i];  
31.     delete[] strNumbers;  
32. }  
33. void main()  
34. {  
35.     int Num;  
36.     cin>>Num;  
37.     int *numbers=new int[Num];  
38.     for(int i=0; i<Num; i++)  
39.         cin>>numbers[i];  
40.     PrintMinNumber(numbers, Num);  
41. }  

代碼二：利用string類。

[cpp]  view plain copy

1. #include <iostream>  
2. #include <string>  
3. #include <sstream>  
4. #include <algorithm>  
5. using namespace std;  
6. bool compare(const string& str1, const string &str2)  
7. {  
8.     string s1=str1+str2;  
9.     string s2=str2+str1;  
10.     return s1<s2;  
11. }  
12. void ComArrayMin(int *pArray, int num)  
13. {  
14.     int i;  
15.     string *pStrArray=new string[num];  
16.     for(i=0; i<num; i++)  
17.     {  
18.         stringstream stream;  
19.         stream<<pArray[i];  
20.         stream>>pStrArray[i];       
21.     }  
22.     sort(pStrArray, pStrArray+num, compare);  
23.     for(i=0; i<num; i++)  
24.         cout<<pStrArray[i];  
25.     cout<<endl;  
26.     delete[] pStrArray;  
27. }  
28. void main()  
29. {  
30.     int Num;  
31.     cin>>Num;  
32.     int *pArray=new int[Num];  
33.     for(int i=0; i<Num; i++)  
34.         cin>>pArray[i];  
35.     ComArrayMin(pArray, Num);  
36. }  

感謝：http://blog.csdn.net/wuzhekai1985/article/details/6704902

           http://blog.csdn.net/xianliti/article/details/5649876