Q題目

華為06年面試題（要求8分鐘完成）

有兩個(gè)數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無序； 要求：通過交換a,b中的元素，使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小。

---

A解法

1.常見錯(cuò)誤邏輯

• 錯(cuò)誤邏輯一：將兩個(gè)數(shù)組合并為一個(gè)數(shù)組，進(jìn)行排序，將前面n個(gè)小的作為數(shù)組a，后面n作為數(shù)組b，a減b得到值，即為最小值。【該思路對題意理解有誤，這里求最小差值，指的是絕對值】

• 錯(cuò)誤邏輯二：同樣是將兩個(gè)數(shù)組合并，然后排序，此時(shí)采用交錯(cuò)的取法，分配給兩個(gè)數(shù)組a和b，比如1,2,3,4，將1和3分給a，2和4非配給b【明顯是錯(cuò)誤的】。還有人采用更加嚴(yán)謹(jǐn)一些的方法，就是沒次交錯(cuò)給兩個(gè)數(shù)組非配值前，比較一下兩個(gè)數(shù)組和的大小，給小的分配大值，此時(shí)1,2,3,4的分配結(jié)果是- - a數(shù)組為：1 , 4 - - b數(shù)組為：2 , 3 。貌似是正確的，但假如最大數(shù)非常大，大到比剩余所有數(shù)字的總和還大呢？此時(shí)應(yīng)該是將前面（n-1）個(gè)最小值與最大值組合在一起。

---

2.最小差值算法

2.1邏輯分析

大概邏輯：將數(shù)組a的每一個(gè)數(shù)依次去與數(shù)組b中的每個(gè)數(shù)，進(jìn)行交換，每次交換完成后分別計(jì)算兩個(gè)數(shù)組的差值（minus），如果差值變大則，不交換，差值變小則交換。此時(shí)時(shí)間復(fù)雜度為O（n！）

詳細(xì)分析：
1）數(shù)組a的第一個(gè)數(shù)與數(shù)組b第一個(gè)數(shù)進(jìn)行交換，交換后兩數(shù)組差值變小，則不做改變了，若變大了，則重新交換回來
2）在上一步基礎(chǔ)上，再用數(shù)組a的第一個(gè)數(shù)（可能是a[0]，也可能交換后的b[0]）去與數(shù)組b的第二個(gè)數(shù)進(jìn)行交換，差值變小，則不作改變，變大，則重新?lián)Q回來，依次進(jìn)行比較
3）數(shù)組a的第一個(gè)數(shù)與數(shù)組b中的所有數(shù)進(jìn)行交換處理后，采用同樣的方法，再用數(shù)組a的第二個(gè)數(shù)與數(shù)組b中的所有數(shù)依次進(jìn)行交換，在比較差值來處理

缺點(diǎn)：計(jì)算量大，有許多重復(fù)的計(jì)算

2.2實(shí)現(xiàn)代碼如下

package 華為面試兩數(shù)組最小差值;import java.util.Arrays;public class Test2 {public static void main(String[] args) {//1.測試數(shù)組a和b // int a[] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 989 }; // int b[] = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 };int a[] = { 1, 3, 5 ,49};int b[] = { 0, 2, 4 ,18};//2.調(diào)用處理數(shù)組的函數(shù)getMinusArray(a, b);//3.打印處理實(shí)現(xiàn)最小差值的數(shù)組a和b--a和b各自的和--System.out.println("交換處理后的數(shù)組a："+Arrays.toString(a));System.out.println("交換處理后的數(shù)組b："+Arrays.toString(b));System.out.println("getSum(a)="+getSum(a));System.out.println("getSum(b)="+getSum(b));System.out.println("交換后a和b的差值：getSum(a)-getSum(b)="+Math.abs(getSum(a)-getSum(b)));}//兩數(shù)組進(jìn)行元素交換實(shí)現(xiàn)最小差值public static void getMinusArray(int[] a, int[] b) {// 數(shù)組a和b的和int suma = getSum(a);int sumb = getSum(b);int startMinus = Math.abs(suma - sumb); // System.out.println("startMinus="+startMinus);int minus = 0;for(int i = 0; i < a.length; i++){for(int j = 0; j < a.length; j++) {//先交換int temp=a[i];a[i]=b[j];b[j]=temp;//交換后的差值minus = Math.abs(getSum(a) - getSum(b));if(minus<startMinus){startMinus = minus;}else{//若交換后，差值比原來大或相等，則不交換--即重新?lián)Q回來int temp2=a[i];a[i]=b[j];b[j]=temp2;}}}}// 求數(shù)組和public static int getSum(int[] arr) {int sum = 0;for (int i : arr) {sum += i;}return sum;} }

運(yùn)行結(jié)果：

3.背包算法

筆者對背包算法不出很清楚
以下粘貼了一部分有關(guān)的背包算法的邏輯分析，僅供參考

舉個(gè)例子，有1,2,3一共3個(gè)數(shù)，將這三個(gè)數(shù)分成兩部分，有3種分法1 | 2,3或者1，2| 3 或者1，3|2，然后計(jì)算每部分所有數(shù)的和，
1 | 2,3 -> 和為1,5，和的差是4
1 2| 3 -> 和為3,3，和的差是0
1 3|2 -> 和為4,2，和的差是2
所以按照1,2| 3分得到的和的差最小。

那么任意給定一個(gè)數(shù)組，如何找出最小值呢？

思路：差最小就是說兩部分的和最接近，或者說與所有數(shù)的和SUM的一半最接近的。

假設(shè)用sum1表示第一部分的和，sum2表示第二部分的和，SUM表示所有數(shù)的和，那么sum1+sum2=SUM。

假設(shè)sum1<sum2 那么SUM/2-sum1 = sum2-SUM/2;

所以我們就有目標(biāo)了，使得sum1<=SUM/2的條件下盡可能的大。
也就是說從n個(gè)數(shù)中選出某些數(shù)，使得這些數(shù)的和盡可能的接近或者等于所有數(shù)的和的一半。

這其實(shí)就是簡單的背包問題了：

背包容量是SUM/2，每個(gè)物體的體積是數(shù)的大小，然后盡可能的裝滿背包。

dp方程：f[i][V] = max(f[i-1][V-v[i]]+v[i], f[i-1][V] ) 說明：f[i][V]表示用前i個(gè)物體裝容量為V的背包能夠裝下的最大值，f[i-1][V-v[i]]+v[i]表示第i個(gè)物體裝進(jìn)背包的情況，f[i-1][V]表示第i件物品不裝進(jìn)背包的情況。

按照dp方程不難寫出代碼：

初始值：f[0][k]=0，f[i][0]=0;

偽代碼

for(i=0;i<n;i++){ for(j=1;j<SUM/2;j++){ f[i][j]=f[i-1][j];if(v[i]<=j && f[i-1][j-v[i]]+v[i]>f[i][j]){ f[i][j]=value[i-1][j-v[i]]+v[i]; } }} 最終差值就是SUM-2*f[n-1][SUM/2];

可參考百度百科：背包算法–http://baike.baidu.com/link?url=f2rLJADvttP0UvcubvHofIGVAcvdl6MV4eQH17fKYeCOLQTECBLsvOIVFKid_OnC1ybaElqARhPqCJjoU-5rqO1D5sKT5OOiEbbNB1EcEeFBYpLzhgYXpjDN2PlWxaU1

總結(jié)

以上是生活随笔為你收集整理的算法--06年华为面试：求两个数组的最小差值（Java实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。