劍指offer 面試題33—把數組排成最小的數

題目：

輸入一個正整數數組，把數組裡面的所有數字連接配接起來排成一個數，列印能拼接出的所有數字中最小的一個。例如輸入數組{3, 32,  321}，則列印這三個數字能排成的最小數字321323。

基本思想：O(nlogn)

兩個數字m和n能拼接數字mn和nm。如果mn<nm，那麼我們應該列印出mn，也就是m應該排在n的前面，我們定義此時m小于n；反之，如果nm<mn，我們定義n小于m。如果mn=nm，m等于n。

如對321和32，排序為32132<32321，是以321<32(這個小于号并非是比較兩個數的實際大小）。

#include <iostream>
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)  //對兩個數進行比較,ab和ba的大小
{
	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;
	int i;

	char** strNumbers = (char**)(new int[length]);
	for(i = 0; i < length; i++)
	{
		strNumbers[i] = new char[g_MaxNumberLength+1];
		sprintf(strNumbers[i], "%d", numbers[i]);  //數字轉為字元串
	}

	qsort(strNumbers, length, sizeof(char*), compare);

	for(i = 0; i < length; i++)
		cout << strNumbers[i];
	cout << endl;

	for(i = 0; i < length; i++)
		delete[] strNumbers[i];

	delete[] strNumbers;

}

int main()
{
	int num;
	cout << "請輸入數組的個數：";
	cin >> num;
	
	int *numbers = new int[num];
	cout << "請進行輸入：";
	for(int i = 0; i < num; i++)
		cin >> numbers[i];

	PrintMinNumber(numbers, num);

	return 0;
}