劍指Offer:面試題33 把數組排成最小的數

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

思路:
我們應該對于給出的兩個數字m和n，需要确定規則m和n哪個應該排序在前面，而不是比誰大誰小。
m和n能拼成mn或者nm，當mn<nm時，我們列印出mn,此時定義<
由于m和n都在int中，而拼接之後可能溢出，是以用字元串法來處理大數問題。
由于mn和nm位數相同，是以比較大小隻需按照字元串大小比較即可。

輸入：
輸入可能包含多個測試樣例。
對于每個測試案例，輸入的第一行為一個整數m (1<=m <=100)代表輸入的正整數的個數。
輸入的第二行包括m個正整數，其中每個正整數不超過10000000。
輸出：
對應每個測試案例，
輸出m個數字能排成的最小數字。
樣例輸入：
3
23 13 6
2
23456 56
樣例輸出：
13236
2345656
*/

/*
關鍵:
1 我們應該對于給出的兩個數字m和n，需要确定規則m和n哪個應該排序在前面，而不是比誰大誰小。
m和n能拼成mn或者nm，當mn<nm時，我們列印出mn,此時定義<
由于m和n都在int中，而拼接之後可能溢出，是以用字元串法來處理大數問題。
由于mn和nm位數相同，是以比較大小隻需按照字元串大小比較即可。
2  char** strNumbers = (char**)(new int[iLen]);//經典，這裡定義二級指針，strNumbers是指向字元指針的指針，而字元指針又指向每個字元串

3  for(int i = 0 ; i < iLen ; i++)//對每個字元指針new一下，然後寫入整數
 {
  strNumbers[i] = new char[MAXLEN + 1];
  sprintf(strNumbers[i],"%d",pArr[i]);//用字元串解決大數問題
4  qsort(strNumbers,iLen,sizeof(char*),compare);
//void qsort(void* buf,size_t num,size_t size,int(*compare)(const void*,const void*)),qsort一半适用于二級字元指針的字元數組時間比較，sort不行
5  for(int k = 0 ; k < iLen ; k++)//注意先删除一級指針，再删除二級指針
 {
  delete[] strNumbers[k];
 }
 delete[] strNumbers;
6 int compare(const void* str1,const void* str2)//qsort比較函數所用形參必須是const void*
7 strcpy(strNum1,*(const char**)str1);//注意，如果改成strcpy(strNum1,(const char*)str1)，是不能實作排序的，不知道為什麼 ?
 strcat(strNum1,*(const char**)str2);
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

const int MAXSIZE = 101;
const int MAXLEN = 10;

//int compare(const char* str1,const char* str2)
int compare(const void* str1,const void* str2)//qsort比較函數所用形參必須是const void*
{
 char strNum1[2*MAXLEN + 1];
 char strNum2[2*MAXLEN + 1];
 strcpy(strNum1,*(const char**)str1);//注意，如果改成strcpy(strNum1,(const char*)str1)，是不能實作排序的，不知道為什麼 ?
 strcat(strNum1,*(const char**)str2);
 strcpy(strNum2,*(const char**)str2);
 strcat(strNum2,*(const char**)str1);
 return strcmp(strNum1,strNum2);
}

void printMinNum(int* pArr,int iLen)
{
 if(!pArr || iLen < 1 || iLen > 100)
 {
  return;
 }
 char** strNumbers = (char**)(new int[iLen]);//經典，這裡定義二級指針，strNumbers是指向字元指針的指針，而字元指針又指向每個字元串
 for(int i = 0 ; i < iLen ; i++)//對每個字元指針new一下，然後寫入整數
 {
  strNumbers[i] = new char[MAXLEN + 1];
  sprintf(strNumbers[i],"%d",pArr[i]);//用字元串解決大數問題
 }
 //sort(strNumbers,strNumbers + iLen,compare);//采用我們自定義的比較函數進行比較
 qsort(strNumbers,iLen,sizeof(char*),compare);//void qsort(void* buf,size_t num,size_t size,int(*compare)(const void*,const void*)),qsort一半适用于二級字元指針的字元數組時間比較，sort不行
 for(int j = 0 ; j < iLen ; j++)
 {
  printf("%s",strNumbers[j]);
 }
 printf("\n");
 for(int k = 0 ; k < iLen ; k++)//注意先删除一級指針，再删除二級指針
 {
  delete[] strNumbers[k];
 }
 delete[] strNumbers;
}

void process()
{
 int n;
 while(EOF != scanf("%d",&n))
 {
  if(n < 1 || n > 100)
  {
   continue;
  }
  int iArr[MAXSIZE];
  for(int i = 0 ; i < n ; i++)
  {
   scanf("%d",&iArr[i]);
  }
  printMinNum(iArr,n);
 }
 
}

int main(int argc,char* argv[])
{
 process();
 getchar();
 return 0;
}