原文作者的解法不錯(cuò)，我一開始沒想到。先貼原文，然后再把我的方法詳細(xì)說下。

?

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

?

==============? 以下內(nèi)容引自原文? ===============================

?

分析：這是09年6月份百度新鮮出爐的一道面試題，從這道題我們可以看出百度對應(yīng)聘者在算法方面有很高的要求。m和n，我們需要確定一個(gè)規(guī)則m和n哪個(gè)更大，而不是僅僅只是比較這兩個(gè)數(shù)字的數(shù)值哪個(gè)更大。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í)是希望我們能找到一個(gè)排序規(guī)則，根據(jù)這個(gè)規(guī)則排出來的數(shù)組能排成一個(gè)最小的數(shù)字。要確定排序規(guī)則，就得比較兩個(gè)數(shù)字，也就是給出兩個(gè)數(shù)字

根據(jù)題目的要求，兩個(gè)數(shù)字

接下來我們考慮怎么去拼接數(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 strings

??? char** 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 compare

??? qsort(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);

}

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

?

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

?

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

?

?

1.??????

?

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

?

?

2.?????? 對稱性。如果a小于b，則ab

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。我們在序列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。我們在序列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è)不成立，我們的算法是正確的。

?

?

==============? 以上內(nèi)容引自原文? ===============================

?

?

下面寫我的思路。

?

剛拿到這題，我沒想到用字符串來做，而是想把整數(shù)拆開成一位一位的數(shù)字來進(jìn)行比較。這種方法在原文的評論中，有其他人也是這么想的。

原文的分析已經(jīng)說得比較明白了，這個(gè)題其實(shí)就是要明確一種兩個(gè)數(shù)之間的比較策略，也就是一組數(shù)的排序規(guī)則，具體點(diǎn)說，就是要重寫compare方法，如果是java語言，只要重載compareTo方法，然后用sort方法就行了。

?

假設(shè)有兩個(gè)數(shù)：A和B，其中，A由m個(gè)數(shù)字組成，表示成a₁a₂...a_m,B由n個(gè)數(shù)字組成，表示成b₁b₂...b_n.比較的規(guī)則是這樣的,從左到右比較，即從最高位開始，到最低位（個(gè)位）

1、如果a_i= b_i,則比較下一位數(shù)；

2、如果a_i< b_i,則A應(yīng)該排到B前面；

3、如果A的所有位和B的前m位相同，即a₁=b₁,a₂=b₂,...,a_m=b_m,另外，n>m。則繼續(xù)比較a₁和b_m+1。

利用上面那個(gè)規(guī)則進(jìn)行比較，直到確定A和B之間的關(guān)系。

?

偽代碼：

[c-sharp] view plaincopy //偽代碼????int?compare(int?A,int?B){????????m?=?A的位數(shù);??????n?=?B的位數(shù);???????????k?=?min(m,n);????????for?i=[1,k]{??????????if?a[i]