把數(shù)組排成最小的數(shù)--總結

時間：2019-07-09 13:24:01

關鍵字：數(shù)組

手機看文章

掃描二維碼
隨時隨地手機看文章

[導讀]原文作者的解法不錯，我一開始沒想到。先貼原文，然后再把我的方法詳細說下。?題目：輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)，輸出能排出的所有數(shù)字中最小的一個。例如輸入數(shù)組{32, ?321}，則輸出

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

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

==============? 以下內容引自原文? ===============================

分析：這是09年6月份百度新鮮出爐的一道面試題，從這道題我們可以看出百度對應聘者在算法方面有很高的要求。m和n，我們需要確定一個規(guī)則m和n哪個更大，而不是僅僅只是比較這兩個數(shù)字的數(shù)值哪個更大。m和n排成的數(shù)字mn和nm，如果mn<nm，那么我們應該輸出mn，也就是m應該排在n的前面，也就是m小于n；反之，如果nm<mn，n小于m。如果mn==mn，m等于n。

這道題其實是希望我們能找到一個排序規(guī)則，根據(jù)這個規(guī)則排出來的數(shù)組能排成一個最小的數(shù)字。要確定排序規(guī)則，就得比較兩個數(shù)字，也就是給出兩個數(shù)字

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

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

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

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

// 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ù)字。

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

首先我們需要證明之前定義的比較兩個數(shù)字大小的規(guī)則是有效的。一個有效的比較需要三個條件：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。當a和b用十進制表示的時候分別為l位和m位時，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。當c表示成十進制時為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個數(shù)按照前面的排序規(guī)則排好順序之后，表示為A₁A₂A₃…A_n。我們假設這樣排出來的兩個數(shù)并不是最小的。即至少存在兩個x和y（0<x<y<n），交換第x個數(shù)和地y個數(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（這個實際上也需要證明。感興趣的讀者可以自己試著證明）。我們就這樣一直把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。這和我們的假設的A₁A₂…A_y…A_x…A_n <A₁A₂…A_x…A_y…A_n相矛盾。

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

==============? 以上內容引自原文? ===============================

下面寫我的思路。

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

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

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

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

2、如果a_i< b_i,則A應該排到B前面；

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

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

偽代碼：

[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]