面試題33：把數組排成最小的數--《劍指offer》

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

這題如果按照一般的全排列，n個數字是n!個排列，實在是行不通...

這時我們需要一個排序規則：

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

按照這個思想（下述是書中代碼）：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>

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;

	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]);  //數字轉為字元串
	}

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

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

	for(int 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;
}
           

如上截圖，輸出也是正确的，至于詳細證明，不再多言...見諒

O(∩_∩)O