華為機試題—把數組排成最小的數 c++

題目描述：

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

輸入：

輸入可能包含多個測試樣例。

對于每個測試案例，輸入的第一行為一個整數m (1<=m <=100)代表輸入的正整數的個數。

輸入的第二行包括m個正整數，其中每個正整數不超過10000000。

輸出：

對應每個測試案例，

輸出m個數字能排成的最小數字。

樣例輸入：

3

23 13 6

2

23456 56

樣例輸出：

13236

2345656

注：markdownpad2中，一行文字需要換行,隻需要在行末尾加上兩個空格即可。

解析 ：按照整數形式，将若幹個數字連接配接起來很麻煩，是以我們可以将整數轉化為字元串，這樣連接配接起來我們可以使用庫函數。然後将字元串數組進行排序。 這裡注意的是字元串的比較函數需要重新定義，不是比較a和b，而是比較ab與 ba。如果ab < ba，則a < b；如果ab > ba，則a > b；如果ab = ba，則a = b。比較函數的定義是本解決方案的關鍵。這道題其實就是希望我們能找到一個排序規則，根據這個規則排出來的數組能排成一個最小的數字。

源碼

#include <iostream>
#include <math.h>
#include <assert.h>
using namespace std;
const int len =10;
char strs[100][len];
char comstr1[2*len];
char comstr2[2*len];

int mycompare(const void *str1,const void *str2)
{
    strcpy(comstr1,(char*)str1);
    strcat(comstr1,(char*)str2);

    strcpy(comstr2,(char*)str2);
    strcat(comstr2,(char*)str1);
    return strcmp(comstr1,comstr2);



void printfminnum(int *nums,int num)
{
    assert(nums);
    int i;
    for(i=0;i<num;i++)
        itoa(nums[i],strs[i],10);
      //sprintf(strs[i],"%d",nums[i]); 将nums[i]轉化成10進制表示的字元串 
    qsort(strs,num,10*sizeof(char),mycompare);
    for(i=0;i<num;i++)  
        printf("%s",strs[i]);  
    printf("\n"); 
}
int main()
{

    int nums[100];
    int m;//數組元素個數
    cin>>m;
    for(int i=0;i<m;i++)
      cin>>nums[i];
    printfminnum(nums,m);

}
           

注：markdownpad2中加入代碼塊可以在代碼塊前後加

“```”

或者Tab鍵 空四格

題目延伸：

1.

void qsort(void *base,int nelem,int width,int (*fcmp)(const void *,const void *));
           

參數：

1 待排序數組首位址

2 數組中待排序元素數量

3 各元素的占用空間大小

4 指向函數的指針，用于确定排序的順序

舉例：

對一個長為1000的數組進行排序時，int a[1000]; 那麼base應為a，num應為 1000，width應為 sizeof(int)，comp函數随自己的命名。

qsort(a,1000,sizeof(int),comp);
int comp(const void*a,const void*b)
{
return *(int*)a-*(int*)b;
}
           

2.

itoa()功能：将任意類型的數字轉換為字元串。在

<stdlib.h>

中與之有相反功能的函數是atoi。itoa()不是C标準庫中的函數，而是Windows平台下擴充的，标準庫中有sprintf()，功能比這個更強，用法跟printf()類似,以後專門學習：

char str[255];
sprintf(str, "%x", 100); //将100轉為16進制表示的字元串。