今天朋友發來一道很特別的題目：
題目：有兩個數組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
