今天朋友发来一道很特别的题目：
题目：有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小。
我乍一看这个题感觉眼熟……和国内各种C语言考试基本上差不多，不过仔细一看似乎还有点难度，不像那种一看就有头绪的问题。好吧，一问才知道，这是华为的一道面试题目。
毕竟是面试，所以还是稍微有点难度的。——但毕竟是国内啊……这个题目也真是向老谭致了足够多的敬了。考虑到它主要考的是算法，那么就和语言无关了，我就用我最熟悉的 Swift 来完成它。
其实这道题有误导啊，它故意强调了“无序”和“交换”让你去想如何计算——其实，只要打乱重排就好了——注意数组的长度要固定——我想这就是为什么数组的大小都为相同的n。另外说的那么复杂，其实目的就是说两个数组里的数字加起来要尽可能的接近罢了，所以，我就先写了个遍历数组求和的函数备用：
|
1 2 3 4 5 6 7 |
func sum(array:Array<Int>)->Int { var sum = 0 for i in array { sum += i } return sum } |
这个函数接收一个数组来遍历求和，然后把结果返回。
然后呢，我设定了两个长度相同的数组：
|
1 2 |
var arrayA = [1,3,5,300,51,3,5,300,5] var arrayB = [800,9,9,7,6800,9,9,7,6] |
这里我们都默认数字类型是整形，因为好计算，其实算法也可以应用与小数，这一点题中没有给出明确的说明，但考虑到可能要用C语言实现，我们还是不要撸泛型了先。
首先，我们写一个函数用来处理这两个数组，最终返回一个带有两个数组的元组。这个元组里就包含了两个经过互换元素的数组，他们的和应当尽可能地接近——即差要尽可能等于零。
|
1 2 |
func balance(arrayA arrayA:Array<Int>,arrayB:Array<Int>)->(Array<Int>,Array<Int>) { ｝ |
然后，不是对比和交换——这不是排序——好吧，其实某种意义上来说这还是排序，我们只需要把数组打散放入池中，然后依次从大到小取出分别放入两个数组就好了。
数组依次分配
可是随后我就发现了这个方法的一个bug！那就是如果我的数组不是平均的呢？比如其中某个数组里有个极大值，那结果就不这么理想了：
如果有极大数或者极小数的时候
而我们期望的结果则是有极大数的一边都是较小的数补齐，而另一边则是剩下尽可能大的数字来填充，这样两者之间的差才最小：
这才是我们期望的结果
那么怎么来判断呢？我们只需要判断数组（元素之和）哪个大哪个小不就行了？我们之前不就恰好写了一个求数组元素之和的函数吗，这不就派上了用场：）
那么现在我们只需要实现把传入的数组打碎再重组排序放入那个 Pool 里边就好了！
这里我用了一个结构体来做了一个堆栈，把排序好的数组扔进去，这样会很直观——其实你可以直接用数组，只不过那样看起来不太好看就是了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
struct Stack { var storeArray:Array<Int> init (arr:Array<Int>) { storeArray = arr } mutating func push(number:Int) { storeArray.insert(number, atIndex: 0) } mutating func pop()->Int { let tmp = storeArray[0] storeArray.removeAtIndex(0) return tmp } } |
那么，配合堆栈，我们的函数就应该是这样：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
func balance(arrayA arrayA:Array<Int>,arrayB:Array<Int>)->(Array<Int>,Array<Int>) { let tmp = arrayA + arrayB var stack = Stack(arr: tmp.sort(>)) for _ in 1...(arrayLength * 2) { if sum(a) <= sum(b) { a.append(stack.pop()) } else { b.append(stack.pop()) } } return (a,b) } |
等等，这样好像哪里不对……运行的结果是这样的：
|
1 2 |
[6800] [800, 300, 300, 51, 9, 9, 9, 9, 7, 7, 6, 5, 5, 5, 3, 3, 1] |
哈哈，看来我们需要一个变量来追踪一下数组的长度，不然分分钟跑题啊！
所以说，如果数组的长度不同，那么我们的函数也不应该执行，那么我们增加一个判断，如果参数不正确（也就是说，输入的两个数组长度不同），函数就不执行，避免数组越界。
那么，们的函数最终的结果是这样的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
func balance(arrayA arrayA:Array<Int>,arrayB:Array<Int>)->(Array<Int>,Array<Int>) { let arrayLength = arrayA.count let tmp = arrayA + arrayB guard tmp.count == arrayLength * 2 else { print("This arrays's length NOT same!\n\t↓") return (arrayA,arrayB) } var a:[Int] = [] var b:[Int] = [] var stack = Stack(arr: tmp.sort(>)) for _ in 1...(arrayLength * 2) { if sum(a) <= sum(b) { if a.count == arrayLength { b.append(stack.pop()) continue } a.append(stack.pop()) } else { if b.count == arrayLength { a.append(stack.pop()) continue } b.append(stack.pop()) } } return (a,b) } |
这样，我们就得到了最终的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
var arrayA = [1,3,5,300,51,3,5,300,5] var arrayB = [800,9,9,7,6800,9,9,7,6] struct Stack { var storeArray:Array<Int> init (arr:Array<Int>) { storeArray = arr } mutating func push(number:Int) { storeArray.insert(number, atIndex: 0) } mutating func pop()->Int { let tmp = storeArray[0] storeArray.removeAtIndex(0) return tmp } } func balance(arrayA arrayA:Array<Int>,arrayB:Array<Int>)->(Array<Int>,Array<Int>) { let arrayLength = arrayA.count let tmp = arrayA + arrayB guard tmp.count == arrayLength * 2 else { print("This arrays's length NOT same!\n\t↓") return (arrayA,arrayB) } var a:[Int] = [] var b:[Int] = [] var stack = Stack(arr: tmp.sort(>)) for _ in 1...(arrayLength * 2) { if sum(a) <= sum(b) { if a.count == arrayLength { b.append(stack.pop()) continue } a.append(stack.pop()) } else { if b.count == arrayLength { a.append(stack.pop()) continue } b.append(stack.pop()) } } return (a,b) } func sum(array:Array<Int>)->Int { var sum = 0 for i in array { sum += i } return sum } let result = balance(arrayA: arrayA, arrayB: arrayB) print(result.0) print(result.1) |
代码执行的结果是：
|
1 2 |
[6800, 7, 6, 5, 5, 5, 3, 3, 1] [800, 300, 300, 51, 9, 9, 9, 9, 7] |
本文由 落格博客 原创撰写：落格博客 » 一道 华为 面试 的 编程算法 题
转载请保留出处和原文链接：https://www.logcg.com/archives/1461.html
