Friend sent today a very special topic：
Topics：There are two array a,b，Size n,Any of the values of the array elements，Disorder；
Requirements：Through the exchange of a,Elements in the b，Elements of array a and b elements in the array, and the difference between the minimum。
I feel familiar at first glance the problem ... ... And domestic c exams almost，But a closer look seems to be a bit more difficult，Do not look like that has a clue what the problem。Ok，I asked to know，This is Huawei's interview questions。
Is, after all, interviews，So it is a little difficult。--But domestic ... ... This topic is really enough respect to the old Tan。Taking into account the main test is the algorithm，Then-and language-independent，I will use my most familiar with Swift to complete it。
In fact, this question is misleading，It deliberately stresses the "disorder" and "swap" makes you think about how to calculate--，Just disrupt rearrangement--pay attention to the length of the array to be fixed--I think this is why the size of the array to the same n。Also says that complex，Purpose is to say the figures add up in the two arrays to be as close as possible to，So，I wrote a function that sums the counting group backup：
|
1 2 3 4 5 6 7 |
func sum(array:Array<Int>)->Int { var sum = 0 for i in array { sum += i } return sum } |
This function accepts an array to loop through the summation，And then return the results。
Then what，I set up two arrays of the same length：
|
1 2 |
var arrayA = [1,3,5,300,51,3,5,300,5] var arrayB = [800,9,9,7,6800,9,9,7,6] |
Here we have the default numeric type is plastic，Because a good calculation，Algorithms can also be used with decimal，This problem did not give clear instructions，But taking into account possible c language implementation，We don't blow the generic。
First of all，We wrote a function to handle the two arrays，Return a tuple with two arrays。The tuple contains two interchangeable elements in an array of，And they should be as close as possible--that is, as far as possible equal to zero。
|
1 2 |
func balance(arrayA arrayA:Array<Int>,arrayB:Array<Int>)->(Array<Int>,Array<Int>) { ｝ |
then，Not compare and exchange--it's not the sort – well，In fact some sort of sense it is，We just pooled break array，Then removed from big to small in the two arrays in a。
Array in turn assigned
But then I found this method a bug! That's what if I'm not the average of the array? Such as the one in the array has a maximum，That result is not so good：
If there is a significant number or minimum number of time
And the results we expect is a great number of side is a smaller number filled，And the other side is left as large numbers as possible to fill，The difference between them is minimal：
This is the expected result
So how to tell? We just need to determine the array (the sum of the elements) which is the biggest little not on the line? We seek not just before writing a function of sum of array elements，It's not used：）
So now we just need to realize broke up the passed array sorting into the Pool would be nice!
Here I use a structure to make a stack，Throw sort an array of，This is intuitive--you can use arrays，Just don't look too good just。
|
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 } } |
Then，Meet stack，Our function should look like this：
|
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) } |
and many more，This seems wrong ... ... Run is the：
|
1 2 |
[6800] [800, 300, 300, 51, 9, 9, 9, 9, 7, 7, 6, 5, 5, 5, 3, 3, 1] |
Haha，Looks like we need a variable to keep track of the length of the array，Or minutes are missing!
So，If the length of the array is different，So our function should not perform，Then we add a judge，If the parameter is incorrect(In other words，Enter two arrays of different lengths)，Function is not performed，Avoid an array out of bounds。
Then，Function is the end result of this is the：
|
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) } |
Such，We have the final code：
|
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) |
Code execution results：
|
1 2 |
[6800, 7, 6, 5, 5, 5, 3, 3, 1] [800, 300, 300, 51, 9, 9, 9, 9, 7] |
Original article written by Gerber drop-off：R0uter's Blog » A programming algorithms Huawei interview questions
Reproduced Please keep the source and description link：https://www.logcg.com/archives/1461.html
