注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(41)-把数组排成最小的数[算法]  

2009-06-21 19:41:33|  分类: 数字游戏 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{32,  321},则输出这两个能排成的最小数字32132请给出解决问题的算法,并证明该算法。

分析:这是096月份百度新鲜出炉的一道面试题,从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

这道题其实是希望我们能找到一个排序规则,根据这个规则排出来的数组能排成一个最小的数字。要确定排序规则,就得比较两个数字,也就是给出两个数字mn,我们需要确定一个规则mn哪个更大,而不是仅仅只是比较这两个数字的数值哪个更大。

根据题目的要求,两个数字mn排成的数字mnnm,如果mn<nm,那么我们应该输出mn,也就是m应该排在n的前面,也就是m小于n;反之,如果nm<mnn小于m。如果mn==mnm等于n

接下来我们考虑怎么去拼接数字,即给出数字mn,怎么得到数字mnnm并比较它们的大小。直接用数值去计算不难办到,但需要考虑到的一个潜在问题是mn都在int能表达的范围内,但把它们拼起来的数字mnnm就不一定能用int表示了。所以我们需要解决大数问题。一个非常直观的方法就是把数字转换成字符串。

另外,由于把数字mn拼接起来得到的mnnm,它们所含有的数字的个数肯定是相同的。因此比较它们的大小只需要按照字符串大小的比较规则就可以了。

基于这个思路,我们可以写出下面的代码:

// Maxinum int number has 10 digits in decimal system

const int g_MaxNumberLength = 10;

 

// String buffers to combine two numbers

char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];

char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];

 

// Given an array, print  the minimum number

// by combining all numbers in the array

void PrintMinNumber(int* numbers, int length)

{

    if(numbers == NULL || length <= 0)

        return;

 

    // Convert all numbers as strings

    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]);

    }

 

    // Sort all strings according to algorithm in function compare

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

 

    for(int i = 0; i < length; ++i)

        printf("%s", strNumbers[i]);

    printf("\n");

 

    for(int i = 0; i < length; ++i)

        delete[] strNumbers[i];

    delete[] strNumbers;

}

 

// Compare two numbers in strNumber1 and strNumber2

// if [strNumber1][strNumber2] > [strNumber2][strNumber1],

// return value > 0

// if [strNumber1][strNumber2] = [strNumber2][strNumber1],

// return value = 0

// if [strNumber1][strNumber2] < [strNumber2][strNumber1],

// return value < 0

int compare(const void* strNumber1, const void* strNumber2)

{

    // [strNumber1][strNumber2]

    strcpy(g_StrCombine1, *(const char**)strNumber1);

    strcat(g_StrCombine1, *(const char**)strNumber2);

 

    // [strNumber2][strNumber1]

    strcpy(g_StrCombine2, *(const char**)strNumber2);

    strcat(g_StrCombine2, *(const char**)strNumber1);

 

    return strcmp(g_StrCombine1, g_StrCombine2);

}

上述代码中,我们在函数compare中定义比较规则,并根据该规则用库函数qsort排序。最后把排好序的数组输出,就得到了根据数组排成的最小的数字。

找到一个算法解决这个问题,不是一件容易的事情。但更困难的是我们需要证明这个算法是正确的。接下来我们来试着证明。

首先我们需要证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较需要三个条件:1.自反性,即a等于a2.对称性,即如果a大于b,则b小于a3.传递性,即如果a小于bb小于c,则a小于c。现在分别予以证明。

1.      

自反性。显然有aa=aa,所以a=a

2.       对称性。如果a小于b,则ab<ba,所以ba>ab。因此b大于a

3.       传递性。如果a小于b,则ab<ba。当ab用十进制表示的时候分别为l位和m位时,ab=a×10m+bba=b×10l+a。所以a×10m+b<b×10l+a。于是有a×10m-a< b×10l –b,即a(10m -1)<b(10l -1)。所以a/(10l -1)<b/(10m -1)

如果b小于c,则bc<cb。当c表示成十进制时为m位。和前面证明过程一样,可以得到b/(10m -1)<c/(10n -1)

所以a/(10l -1)< c/(10n -1)。于是a(10n -1)<c(10l -1),所以a×10n +c<c×10l +a,即ac<ca

所以a小于c

在证明了我们排序规则的有效性之后,我们接着证明算法的正确性。我们用反证法来证明。

我们把n个数按照前面的排序规则排好顺序之后,表示为A1A2A3…An。我们假设这样排出来的两个数并不是最小的。即至少存在两个xy0<x<y<n),交换第x个数和地y个数后,A1A2…Ay…Ax…An<A1A2…Ax…Ay…An

由于A1A2…Ax…Ay…An是按照前面的规则排好的序列,所以有Ax<Ax+1<Ax+2<…<Ay-2<Ay-1<Ay

由于Ay-1小于Ay,所以Ay-1Ay<AyAy-1。我们在序列A1A2…Ax…Ay-1Ay…An交换Ay-1Ay,有A1A2…Ax…Ay-1Ay…An<A1A2…Ax…AyAy-1…An(这个实际上也需要证明。感兴趣的读者可以自己试着证明)。我们就这样一直把Ay和前面的数字交换,直到和Ax交换为止。于是就有A1A2…Ax…Ay-1Ay…An<A1A2…Ax…AyAy-1…An< A1A2…Ax…AyAy-2Ay-1…An<…< A1A2…AyAx…Ay-2Ay-1…An

同理由于Ax小于Ax+1,所以AxAx+1<Ax+1Ax。我们在序列A1A2…AyAxAx+1…Ay-2Ay-1…An仅仅只交换AxAx+1,有A1A2…AyAxAx+1…Ay-2Ay-1…An<A1A2…AyAx+1Ax…Ay-2Ay-1…An。我们接下来一直拿Ax和它后面的数字交换,直到和Ay-1交换为止。于是就有A1A2…AyAxAx+1…Ay-2Ay-1…An<A1A2…AyAx+1Ax…Ay-2Ay-1…An<…< A1A2…AyAx+1Ax+2…Ay-2Ay-1Ax…An

所以A1A2…Ax…Ay…An< A1A2…Ay…Ax…An。这和我们的假设的A1A2…Ay…Ax…An <A1A2…Ax…Ay…An相矛盾。

所以假设不成立,我们的算法是正确的。

 

本文已经收录到《剑指Offer——名企面试官精讲典型编程题》一书中,有改动,书中的分析讲解更加详细。欢迎关注。

本题已被九度Online Judge系统收录,欢迎读者移步到http://ac.jobdu.com/hhtproblems.php在线测试自己的代码。

博主何海涛对本博客文章享有版权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。

  评论这张
 
阅读(24582)| 评论(62)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017