一个朋友面试时遇到的算法题(怎么组合后得到最大整数)

    最近工作比较忙,且工作重心改变,不再直接从事编程方面的工作。目前的工作,对我来说是个新领域,

我需要不断学习才能跟上脚步。人生就是充满挑战,逆水行舟,不进则退。 以下是一个朋友在北京面试时,

考官出的一道题,他当时遇到点困难,回来就跟我交流了,

题目如下:

一个正整数数组:如, 14 32 133 152

将其串起来得到能表示的最大整数(这里就是3215214133)

    看到这个题我立马想到,这个题毋庸置疑是“排序”。而且这个题很阴险,故意给了一组简单情况的数字用例。 串起来得到的最大整数,

当然迅速想到以下几条排序规则:

1,所有正整数中第一个数字最大的,就要排在最前面,而不用管这个数字到底有多长。

2,将最大的那个数提取出来后,继续执行1。

3,当遇见多个正整数的第一个数字相同时,则比较第二个数字,第二个数字最大的数排前面。

    这里第3条规则是存在问题的。例如:32,3。这两个数字用第三条规则时,会发现无法进行下去,因为3这个正整数不存在第二个数字。

如果你不太小心,就会认为没有数字时,应该用0来补足。那么利用第三条规则得到的最终最大结果是“323”,而正确结果应该是“332”。

由于第三条规则有问题,接下来修复第三条规则。

    通常地,小学生们(也包括你我)比较两个正整数大小时,会有如下的思维:

1,两个正整数,位数多的 > 位数少的。

2,相同位数的两个正整数,先比较最高位,最高位大则正整数大。

3,最高位相同的,则比较次高位,以此类推,直到比较完。最终无法分出大小的,则是相等。

以上3条规则,规则1可以融入到规则2和3中。只需要将位数少的高位补若干个0,达到两个数位数相同即可。 有了这个小学生都知道的规则基础,

我知道,只要能把比较的两个数位数对齐,那条错误的规则“3”就正确了。

    那怎么将两个不同的正整数对齐呢。我这里直接给出我的答案。

对齐方式: 数字有0-9,共10种。我现在再加入一个转基因新品种,叫做“*”。 这个“*”定义为,数字abc*  这个*比自己的首数字“a”大,但是比“a+1”小。

如果a=9,那么*比所有的数字都大。 当两个数字“abcd”和“ef”,它们需要对齐时,即可在位数少的数字的低位补若干个“*”,达到位数一致。

这时“ef”变成了“ef**”。 这时候就可以用那3条规则由大到小排序了,排序后就得到了最大的结果。

    后来我又想到了另外一个方式来做这个题。

方式二:

假设正整数A和正整数B,我们为了得到组合后最大的数,无非就是比较AB和BA哪个大。 通过这种方式,可以比较正整数A和正整数B的大小。

那么我们得到了一个compare函数。

compare(A,B)

{  

  return AB>BA;

}

有了这个比较函数,就可以用你想用的任何排序算法来得到正确答案。

谢谢大家看到最后,本人水平有限,如有失误之处欢迎指点。本人邮箱 rongguozhen@foxmail.com

原文地址:https://www.cnblogs.com/MrWrong/p/3986158.html