您好,登錄后才能下訂單哦!
這是一道經(jīng)典的面試題,初次看到這道題我們可能會想到全排列,然后把每個排列拼起來,最后我們求出拼出來的最小值就可以了,下面我們說一種更快的算法。
其實我們可以找出一種排序規(guī)則,數(shù)組根據(jù)這個排序規(guī)則就能排成一個最小的數(shù)。我們要確定排序規(guī)則,就要比較兩個數(shù)字,比如m和n,我們需要一個規(guī)則判斷m和n哪個應(yīng)該排在前面,并不僅僅是比較這兩個數(shù)的大小。
關(guān)于這道題我們還需要考慮的一個潛在問題是假如m和n都在int的表達范圍內(nèi),那么它們拼接之后呢?超出int的范圍怎么辦?這些都是我們需要考慮的問題,這是一個隱藏的大數(shù)問題。我們都知道,我們可以通過把數(shù)字轉(zhuǎn)換成字符串的形式來解決大數(shù)問題,這樣多大的位數(shù)我們都能裝下,裝換成字符串后,比較他們拼接成的數(shù)字的大小就直接按照字符串的大小比較規(guī)則來就可以了。下面我們看看具體的代碼。
#include<stdio.h> #include <stdlib.h> #include <string.h> const int g_MaxNumberLength = 10; //×××所能表示的最大位數(shù) char *g_StrCombine1 = new char[g_MaxNumberLength*2 + 1]; //用來存放超過×××位數(shù)的字符串 char *g_StrCombine2 = new char[g_MaxNumberLength*2 + 1]; int compare(const void* strNumber1, const void* strNumber2)//自定義比較函數(shù),比較兩個字符串大小 { 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)>0;//注意這里大于0默認(rèn)升序排列,小于0降序 } void PrintfMinNumber(int* number, int length) { if (number == NULL || length < 0) { return; } char** strNumbers = (char**)(new int[length]); //定義一個二維數(shù)組 int i = 0; for (; i < length; ++i) { strNumbers[i] = new char[g_MaxNumberLength + 1]; // 數(shù)組里面每個元素都是char類型的指針 sprintf(strNumbers[i], "%d", number[i]); } qsort(strNumbers, length, sizeof(char*), compare); i = 0; for (; i < length; i++) { printf("%s", strNumbers[i]); } printf("\n"); i = 0; for (; i < length; ++i) { delete[] strNumbers[i]; } delete[] strNumbers; } int main() { int arr[3] = { 12, 3, 4};//這里數(shù)組內(nèi)容自己隨便給就可以 int len = sizeof(arr) / sizeof(arr[0]); PrintfMinNumber(arr, len); return 0; }
假如是上面數(shù)組的內(nèi)容,我在vs2013下運行結(jié)果如下:
我們可以看到,正如我們預(yù)期的那樣,把數(shù)組內(nèi)容排成了我們需要的最小的整數(shù)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。