題目：輸入一個(gè)正整數(shù)數(shù)組，將它們連接起來排成一個(gè)數(shù)，輸出能排出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{32,??321}，則輸出這兩個(gè)能排成的最小數(shù)字32132。請(qǐng)給出解決問題的算法，并證明該算法。

分析：這是09年6月份百度新鮮出爐的一道面試題，從這道題我們可以看出百度對(duì)應(yīng)聘者在算法方面有很高的要求。

這道題其實(shí)是希望我們能找到一個(gè)排序規(guī)則，根據(jù)這個(gè)規(guī)則排出來的數(shù)組能排成一個(gè)最小的數(shù)字。要確定排序規(guī)則，就得比較兩個(gè)數(shù)字，也就是給出兩個(gè)數(shù)字m和n，我們需要確定一個(gè)規(guī)則m和n哪個(gè)更大，而不是僅僅只是比較這兩個(gè)數(shù)字的數(shù)值哪個(gè)更大。

根據(jù)題目的要求，兩個(gè)數(shù)字m和n排成的數(shù)字mn和nm，如果mn<nm，那么我們應(yīng)該輸出mn，也就是m應(yīng)該排在n的前面，也就是m小于n；反之，如果nm<mn，n小于m。如果mn==mn，m等于n。

接下來我們考慮怎么去拼接數(shù)字，即給出數(shù)字m和n，怎么得到數(shù)字mn和nm并比較它們的大小。直接用數(shù)值去計(jì)算不難辦到，但需要考慮到的一個(gè)潛在問題是m和n都在int能表達(dá)的范圍內(nèi)，但把它們拼起來的數(shù)字mn和nm就不一定能用int表示了。所以我們需要解決大數(shù)問題。一個(gè)非常直觀的方法就是把數(shù)字轉(zhuǎn)換成字符串。

另外，由于把數(shù)字m和n拼接起來得到的mn和nm，它們所含有的數(shù)字的個(gè)數(shù)肯定是相同的。因此比較它們的大小只需要按照字符串大小的比較規(guī)則就可以了。

基于這個(gè)思路，我們可以寫出下面的代碼：

// Maxinum int number has 10 digits in decimal system const int g_MaxNumberLength = 10;// String buffers to combine two numbers char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1]; char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];// Given an array, print the minimum number // by combining all numbers in the array void PrintMinNumber(int* numbers, int length) {if(numbers == NULL || length <= 0)return;// Convert all numbers as stringschar** strNumbers = (char**)(new int[length]);for(int i = 0; i < length; ++i){strNumbers[i] = new char[g_MaxNumberLength + 1];sprintf(strNumbers[i], "%d", numbers[i]);}// Sort all strings according to algorithm in function compareqsort(strNumbers, length, sizeof(char*), compare);for(int i = 0; i < length; ++i)printf("%s", strNumbers[i]);printf("\n");for(int i = 0; i < length; ++i)delete[] strNumbers[i];delete[] strNumbers; }// Compare two numbers in strNumber1 and strNumber2 // if [strNumber1][strNumber2] > [strNumber2][strNumber1], // return value > 0 // if [strNumber1][strNumber2] = [strNumber2][strNumber1], // return value = 0 // if [strNumber1][strNumber2] < [strNumber2][strNumber1], // return value < 0 int compare(const void* strNumber1, const void* strNumber2) {// [strNumber1][strNumber2]strcpy(g_StrCombine1, *(const char**)strNumber1);strcat(g_StrCombine1, *(const char**)strNumber2);// [strNumber2][strNumber1]strcpy(g_StrCombine2, *(const char**)strNumber2);strcat(g_StrCombine2, *(const char**)strNumber1);return strcmp(g_StrCombine1, g_StrCombine2); }

上述代碼中，我們?cè)诤瘮?shù)compare中定義比較規(guī)則，并根據(jù)該規(guī)則用庫函數(shù)qsort排序。最后把排好序的數(shù)組輸出，就得到了根據(jù)數(shù)組排成的最小的數(shù)字。

找到一個(gè)算法解決這個(gè)問題，不是一件容易的事情。但更困難的是我們需要證明這個(gè)算法是正確的。接下來我們來試著證明。

首先我們需要證明之前定義的比較兩個(gè)數(shù)字大小的規(guī)則是有效的。一個(gè)有效的比較需要三個(gè)條件：1.自反性，即a等于a；2.對(duì)稱性，即如果a大于b，則b小于a；3.傳遞性，即如果a小于b，b小于c，則a小于c。現(xiàn)在分別予以證明。

1.??????

自反性。顯然有 aa=aa，所以 a=a。

2.???????對(duì)稱性。如果a小于b，則ab<ba，所以ba>ab。因此b大于a。

3.???????傳遞性。如果a小于b，則ab<ba。當(dāng)a和b用十進(jìn)制表示的時(shí)候分別為l位和m位時(shí)，ab=a×10^m+b，ba=b×10^l+a。所以a×10^m+b<b×10^l+a。于是有a×10^m-a< b×10^l?–b，即a(10^m?-1)<b(10^l?-1)。所以a/(10^l?-1)<b/(10^m?-1)。

如果b小于c，則bc<cb。當(dāng)c表示成十進(jìn)制時(shí)為m位。和前面證明過程一樣，可以得到b/(10^m?-1)<c/(10ⁿ?-1)。

所以a/(10^l?-1)< c/(10ⁿ?-1)。于是a(10ⁿ?-1)<c(10^l?-1)，所以a×10ⁿ?+c<c×10^l?+a，即ac<ca。

所以a小于c。

在證明了我們排序規(guī)則的有效性之后，我們接著證明算法的正確性。我們用反證法來證明。

我們把n個(gè)數(shù)按照前面的排序規(guī)則排好順序之后，表示為A₁A₂A₃…A_n。我們假設(shè)這樣排出來的兩個(gè)數(shù)并不是最小的。即至少存在兩個(gè)x和y（0<x<y<n），交換第x個(gè)數(shù)和地y個(gè)數(shù)后，A₁A₂…A_y…A_x…A_n<A₁A₂…A_x…A_y…A_n。

由于A₁A₂…A_x…A_y…A_n是按照前面的規(guī)則排好的序列，所以有A_x<A_x+1<A_x+2<…<A_y-2<A_y-1<A_y。

由于A_y-1小于A_y，所以A_y-1A_y<A_yA_y-1。我們?cè)谛蛄?span style="font-family:Calibri">A₁A₂…A_x…A_y-1A_y…A_n交換A_y-1和A_y，有A₁A₂…A_x…A_y-1A_y…A_n<A₁A₂…A_x…A_yA_y-1…A_n（這個(gè)實(shí)際上也需要證明。感興趣的讀者可以自己試著證明）。我們就這樣一直把A_y和前面的數(shù)字交換，直到和A_x交換為止。于是就有A₁A₂…A_x…A_y-1A_y…A_n<A₁A₂…A_x…A_yA_y-1…A_n< A₁A₂…A_x…A_yA_y-2A_y-1…A_n<…< A₁A₂…A_yA_x…A_y-2A_y-1…A_n。

同理由于A_x小于A_x+1，所以A_xA_x+1<A_x+1A_x。我們?cè)谛蛄?span style="font-family:Calibri">A₁A₂…A_yA_xA_x+1…A_y-2A_y-1…A_n僅僅只交換A_x和A_x+1，有A₁A₂…A_yA_xA_x+1…A_y-2A_y-1…A_n<A₁A₂…A_yA_x+1A_x…A_y-2A_y-1…A_n。我們接下來一直拿A_x和它后面的數(shù)字交換，直到和A_y-1交換為止。于是就有A₁A₂…A_yA_xA_x+1…A_y-2A_y-1…A_n<A₁A₂…A_yA_x+1A_x…A_y-2A_y-1…A_n<…< A₁A₂…A_yA_x+1A_x+2…A_y-2A_y-1A_x…A_n。

所以A₁A₂…A_x…A_y…A_n< A₁A₂…A_y…A_x…A_n。這和我們的假設(shè)的A₁A₂…A_y…A_x…A_n?<A₁A₂…A_x…A_y…A_n相矛盾。

所以假設(shè)不成立，我們的算法是正確的。

?

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動(dòng)，書中的分析講解更加詳細(xì)。歡迎關(guān)注。

本題已被九度Online Judge系統(tǒng)收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測(cè)試自己的代碼。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(41)-把数组排成最小的数[算法]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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