【百度面試題】把數(shù)組排成最小的數(shù)

? ? ? 思路：先將整數(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)鍵。這道題其實(shí)就是希望我們能找到一個(gè)排序規(guī)則，根據(jù)這個(gè)規(guī)則排出來的數(shù)組能排成一個(gè)最小的數(shù)字。

? ? ? 證明：為什么這樣排個(gè)序就可以了呢？簡(jiǎn)單證明一下。根據(jù)算法，如果a < b，那么a排在b前面，否則b排在a前面。可利用反證法，假設(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部分看成一個(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的前面。從而得出算法是正確的。

代碼一：利用指針。

#include 
#include 
using namespace std;

const int g_MaxNumberLength=10;
char* g_StrCombine1=new char[g_MaxNumberLength*2+1];
char* g_StrCombine2=new char[g_MaxNumberLength*2+1];

int compare(const void* strNumber1, const void* strNumber2)
{
	strcpy(g_StrCombine1, *(const char**)strNumber1);
	strcat(g_StrCombine1, *(const char**)strNumber2);

	strcpy(g_StrCombine2, *(const char**)strNumber2);
	strcat(g_StrCombine2, *(const char**)strNumber1);

	return strcmp(g_StrCombine1, g_StrCombine2);
}

void PrintMinNumber(int *numbers, int length)
{
	if(numbers==NULL || length<=0)
		return;

	char** strNumbers=(char**)(new int[length]);
	for(int i=0; i>Num;
	int *numbers=new int[Num];
	for(int i=0; i>numbers[i];

	PrintMinNumber(numbers, Num);
}

代碼二：利用string類。

#include 
#include 
#include 
#include 
using namespace std;

bool compare(const string& str1, const string &str2)
{
	string s1=str1+str2;
	string s2=str2+str1;
	return s1>pStrArray[i];		
	}

	sort(pStrArray, pStrArray+num, compare);

	for(i=0; i>Num;
	int *pArray=new int[Num];

	for(int i=0; i>pArray[i];

	ComArrayMin(pArray, Num);

}

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

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