一道 华为 面试 的 编程算法 题

今天朋友发来一道很特别的题目:

题目:有两个数组a,b,大小都为n,数组元素的值任意,无序;
要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小。

我乍一看这个题感觉眼熟……和国内各种C语言考试基本上差不多,不过仔细一看似乎还有点难度,不像那种一看就有头绪的问题。好吧,一问才知道,这是华为的一道面试题目。

毕竟是面试,所以还是稍微有点难度的。——但毕竟是国内啊……这个题目也真是向老谭致了足够多的敬了。考虑到它主要考的是算法,那么就和语言无关了,我就用我最熟悉的 Swift 来完成它。

其实这道题有误导啊,它故意强调了“无序”和“交换”让你去想如何计算——其实,只要打乱重排就好了——注意数组的长度要固定——我想这就是为什么数组的大小都为相同的n。另外说的那么复杂,其实目的就是说两个数组里的数字加起来要尽可能的接近罢了,所以,我就先写了个遍历数组求和的函数备用:

这个函数接收一个数组来遍历求和,然后把结果返回。

然后呢,我设定了两个长度相同的数组:

这里我们都默认数字类型是整形,因为好计算,其实算法也可以应用与小数,这一点题中没有给出明确的说明,但考虑到可能要用C语言实现,我们还是不要撸泛型了先。

首先,我们写一个函数用来处理这两个数组,最终返回一个带有两个数组的元组。这个元组里就包含了两个经过互换元素的数组,他们的和应当尽可能地接近——即差要尽可能等于零。

然后,不是对比和交换——这不是排序——好吧,其实某种意义上来说这还是排序,我们只需要把数组打散放入池中,然后依次从大到小取出分别放入两个数组就好了。

数组依次分配
数组依次分配

可是随后我就发现了这个方法的一个bug!那就是如果我的数组不是平均的呢?比如其中某个数组里有个极大值,那结果就不这么理想了:

如果有极大数或者极小数的时候
如果有极大数或者极小数的时候

而我们期望的结果则是有极大数的一边都是较小的数补齐,而另一边则是剩下尽可能大的数字来填充,这样两者之间的差才最小:

这才是我们期望的结果
这才是我们期望的结果

那么怎么来判断呢?我们只需要判断数组(元素之和)哪个大哪个小不就行了?我们之前不就恰好写了一个求数组元素之和的函数吗,这不就派上了用场:)

那么现在我们只需要实现把传入的数组打碎再重组排序放入那个 Pool 里边就好了!

这里我用了一个结构体来做了一个堆栈,把排序好的数组扔进去,这样会很直观——其实你可以直接用数组,只不过那样看起来不太好看就是了。

那么,配合堆栈,我们的函数就应该是这样:

等等,这样好像哪里不对……运行的结果是这样的:

哈哈,看来我们需要一个变量来追踪一下数组的长度,不然分分钟跑题啊!

所以说,如果数组的长度不同,那么我们的函数也不应该执行,那么我们增加一个判断,如果参数不正确(也就是说,输入的两个数组长度不同),函数就不执行,避免数组越界。

那么,们的函数最终的结果是这样的:

这样,我们就得到了最终的代码:

代码执行的结果是:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.