算法--06年华为面试：求两个数组的最小差值（Java实现）

快来打我* 2022-06-14 06:25 155阅读 0赞

# Q题目 #

**华为06年面试题（要求8分钟完成）**

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

--------------------

# A解法 #

## 1.常见错误逻辑 ##

*  **错误逻辑一**：将两个数组合并为一个数组，进行排序，将前面n个小的作为数组a，后面n作为数组b，a减b得到值，即为最小值。【该思路对题意理解有误，这里求最小差值，指的是绝对值】
 *  **错误逻辑二**：同样是将两个数组合并，然后排序，此时采用交错的取法，分配给两个数组a和b，比如1,2,3,4，将1和3分给a，2和4非配给b【明显是错误的】。还有人采用更加严谨一些的方法，就是没次交错给两个数组非配值前，比较一下两个数组和的大小，给小的分配大值，此时1,2,3,4的分配结果是- - a数组为：1 , 4 - - b数组为：2 , 3 。貌似是正确的，但假如最大数非常大，大到比剩余所有数字的总和还大呢？此时应该是将前面（n-1）个最小值与最大值组合在一起。

--------------------

## 2.最小差值算法 ##

### 2.1逻辑分析 ###

> **大概逻辑：**将数组a的每一个数依次去与数组b中的每个数，进行交换，每次交换完成后分别计算两个数组的差值（minus），如果差值变大则，不交换，差值变小则交换。此时时间复杂度为O（n！）
> 
> **详细分析：**  
> 1）数组a的第一个数与数组b第一个数进行交换，交换后两数组差值变小，则不做改变了，若变大了，则重新交换回来  
> 2）在上一步基础上，再用数组a的第一个数（可能是a\[0\]，也可能交换后的b\[0\]）去与数组b的第二个数进行交换，差值变小，则不作改变，变大，则重新换回来，依次进行比较  
> 3）数组a的第一个数与数组b中的所有数进行交换处理后，采用同样的方法，再用数组a的第二个数与数组b中的所有数依次进行交换，在比较差值来处理
> 
> **缺点：**计算量大，有许多重复的计算

### 2.2实现代码如下 ###

package 华为面试两数组最小差值;
    
    import java.util.Arrays;
    
    public class Test2 {
        public static void main(String[] args) {
            //1.测试数组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.调用处理数组的函数
            getMinusArray(a, b);
    
            //3.打印处理实现最小差值的数组a和b--a和b各自的和--
            System.out.println("交换处理后的数组a："+Arrays.toString(a));
            System.out.println("交换处理后的数组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)));
        }
    
        //两数组进行元素交换实现最小差值
        public static void getMinusArray(int[] a, int[] b) {
            // 数组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{
                        //若交换后，差值比原来大或相等，则不交换--即重新换回来
                        int temp2=a[i];
                        a[i]=b[j];
                        b[j]=temp2;
                    }
                }
            }
        }
    
        // 求数组和
        public static int getSum(int[] arr) {
            int sum = 0;
            for (int i : arr) {
                sum += i;
            }
            return sum;
        }
    }

**运行结果：**

![这里写图片描述][SouthEast]

## 3.背包算法 ##

> 笔者对背包算法不出很清楚  
> **以下粘贴了一部分有关的背包算法的逻辑分析，仅供参考**
> 
> 举个例子，有1,2,3一共3个数，将这三个数分成两部分，有3种分法1 | 2,3或者1，2| 3 或者1，3|2，然后计算每部分所有数的和，  
> 1 | 2,3 -> 和为1,5，和的差是4  
> 1 2| 3 -> 和为3,3，和的差是0  
> 1 3|2 -> 和为4,2，和的差是2  
> 所以按照1,2| 3分得到的和的差最小。
> 
> 那么任意给定一个数组，如何找出最小值呢？
> 
> 思路：差最小就是说两部分的和最接近，或者说与所有数的和SUM的一半最接近的。
> 
> 假设用sum1表示第一部分的和，sum2表示第二部分的和，SUM表示所有数的和，那么sum1+sum2=SUM。

假设sum1<sum2 那么SUM/2-sum1 = sum2-SUM/2;

> 所以我们就有目标了，使得sum1<=SUM/2的条件下尽可能的大。  
> 也就是说从n个数中选出某些数，使得这些数的和尽可能的接近或者等于所有数的和的一半。
> 
> 这其实就是简单的背包问题了：
> 
> 背包容量是SUM/2，每个物体的体积是数的大小，然后尽可能的装满背包。

dp方程：f[i][V] = max(f[i-1][V-v[i]]+v[i], f[i-1][V] ) 
    
    说明：f[i][V]表示用前i个物体装容量为V的背包能够装下的最大值，
        f[i-1][V-v[i]]+v[i]表示第i个物体装进背包的情况，
        f[i-1][V]表示第i件物品不装进背包的情况。

按照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];

**可参考百度百科：[背包算法][Link 1]–[http://baike.baidu.com/link?url=f2rLJADvttP0UvcubvHofIGVAcvdl6MV4eQH17fKYeCOLQTECBLsvOIVFKid\_OnC1ybaElqARhPqCJjoU-5rqO1D5sKT5OOiEbbNB1EcEeFBYpLzhgYXpjDN2PlWxaU1][Link 1]**

[SouthEast]: /images/20220614/7e7f005dcb314c12bb04ea6c40e9eb53.png
[Link 1]: http://baike.baidu.com/link?url=f2rLJADvttP0UvcubvHofIGVAcvdl6MV4eQH17fKYeCOLQTECBLsvOIVFKid_OnC1ybaElqARhPqCJjoU-5rqO1D5sKT5OOiEbbNB1EcEeFBYpLzhgYXpjDN2PlWxaU1