68.把數組排成最小的數。
題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中最小的一個。
例如輸入數組{32, 321}，則輸出這兩個能排成的最小數字32132。
請給出解決問題的算法，並證明該算法。
分析：這是09年6月份百度的一道面試題，
從這道題我們可以看出百度對應聘者在算法方面有很高的要求。
[cpp]
/*
Name:
Copyright:
Author:
Date: 25-06-11 15:19
Description: 把數組排成最小的數（數組、算法）。
題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中
最小的一個。
例如輸入數組{32, 321}，則輸出這兩個能排成的最小數字32132。
請給出解決問題的算法，並證明該算法。
*/
#include<iostream>
#include<iomanip>
using namespace std;
#define N 10 //總共有N個整數
bool cmp_min(char *s1,char *s2)
//算法保證,s1、s2都不是空串
{
const int slen1=strlen(s1);
const int slen2=strlen(s2);
char *tc=(char *)malloc(slen1+slen2+1);//只開辟一個空間
int i;
for(i=0;i<slen2;++i)
tc[i]=s2[i];
for(;i<slen1+slen2;++i)
tc[i]=s1[i-slen2];
tc[i]='\0';
for(i=0;i<slen1;++i)
{
if(s1[i]==tc[i])
continue;
else
{
if(s1[i]>tc[i])
return false;
else
return true;
}
}
for(;i<slen1+slen2;++i)
{
if(s2[i-slen1]==tc[i])
continue;
else
{
if(s1[i-slen1]>tc[i])
return false;
else
return true;
}
}
return false;
}
int sort_partition(char *s[],int p,int r)
{
char *x=s[r];
int i=p-1;
int j;
char *tem;
for(j=p;j<r;++j)
{
if(cmp_min(s[j],x))
{
tem=s[++i];
s[i]=s[j];
s[j]=tem;
}
}
tem=s[++i];
s[i]=x;
s[r]=tem;
return i;
}
void quick_sort(char *s[],int p,int r)
{
int m;
if(p<r)
{
m=sort_partition(s,p,r);
quick_sort(s,p,m-1);
quick_sort(s,m+1,r);
}
}
int main()
{
//z總共有N個整數
int a[N]={123,43,565,1,67,234,9012,1056,2056,2249};
char *s[N];//指針數組
for(int i=0;i<N;++i)
{//轉換為N個字符串
s[i]=(char *)malloc(sizeof(char)*12);
//一個整數用11為來表示
itoa(a[i],s[i],10);
//包含'\0'
}
for(int i=0;i<N;i++)
{
cout<<s[i]<<" ";
}
quick_sort(s,0,9);
cout<<endl;
for(int i=0;i<N;i++)
{
cout<<s[i]<<" ";
}
system("pause");
return 0;
}
/*
Name:
Copyright:
Author:
Date: 25-06-11 15:19
Description: 把數組排成最小的數（數組、算法）。
題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中
最小的一個。
例如輸入數組{32, 321}，則輸出這兩個能排成的最小數字32132。
請給出解決問題的算法，並證明該算法。
*/
#include<iostream>
#include<iomanip>
using namespace std;
#define N 10 //總共有N個整數
bool cmp_min(char *s1,char *s2)
//算法保證,s1、s2都不是空串
{
const int slen1=strlen(s1);
const int slen2=strlen(s2);
char *tc=(char *)malloc(slen1+slen2+1);//只開辟一個空間
int i;
for(i=0;i<slen2;++i)
tc[i]=s2[i];
for(;i<slen1+slen2;++i)
tc[i]=s1[i-slen2];
tc[i]='\0';
for(i=0;i<slen1;++i)
{
if(s1[i]==tc[i])
continue;
else
{
if(s1[i]>tc[i])
return false;
else
return true;
}
}
for(;i<slen1+slen2;++i)
{
if(s2[i-slen1]==tc[i])
continue;
else
{
if(s1[i-slen1]>tc[i])
return false;
else
return true;
}
}
return false;
}
int sort_partition(char *s[],int p,int r)
{
char *x=s[r];
int i=p-1;
int j;
char *tem;
for(j=p;j<r;++j)
{
if(cmp_min(s[j],x))
{
tem=s[++i];
s[i]=s[j];
s[j]=tem;
}
}
tem=s[++i];
s[i]=x;
s[r]=tem;
return i;
}
void quick_sort(char *s[],int p,int r)
{
int m;
if(p<r)
{
m=sort_partition(s,p,r);
quick_sort(s,p,m-1);
quick_sort(s,m+1,r);
}
}
int main()
{
//z總共有N個整數
int a[N]={123,43,565,1,67,234,9012,1056,2056,2249};
char *s[N];//指針數組
for(int i=0;i<N;++i)
{//轉換為N個字符串
s[i]=(char *)malloc(sizeof(char)*12);
//一個整數用11為來表示
itoa(a[i],s[i],10);
//包含'\0'
}
for(int i=0;i<N;i++)
{
cout<<s[i]<<" ";
}
quick_sort(s,0,9);
cout<<endl;
for(int i=0;i<N;i++)
{
cout<<s[i]<<" ";
}
system("pause");
return 0;
}
就是一個快速排序，比較操作采用符號重載的方式，這個題目還是比較有意思的
