首页 > 试题广场 >

有两个数组 A、B,长度都为 N,值为任意整数,无序,要求,

[问答题]
有两个数组 AB,长度都为 N,值为任意整数,无序,要求,通过交换 AB 中的元素,使得 A 数组元素之和与 B 数组元素之和之间的差值最小。完成代码的同时,写出数组 [100,99,98,1,2, 3][1,2,3,4,5,40]交换后的结果。(请用代码实现)
   A[4, 5, 40, 98, 99, 100]
package package1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class A_B {
    List<Integer> path = new ArrayList<>();
    int min=Integer.MAX_VALUE;
    public static List<Integer> new_A;
    public static void main(String[] args) {
        int[] a=new int[]{100,99,98,1,2,3};
        int[] b=new int[]{1,2,3,4,5,40};
        A_B ab= new A_B();
        ab.swapelement(a,b);
        System.out.println(new_A);

    }

    public void swapelement(int[] a, int[] b){
        int len1 = a.length;
        int[] arr = new int[len1*2];
        //
        for(int i=0;i<2*len1;i++){
            if(i<len1){
                arr[i]=a[i];
            }else{
                arr[i]=b[i-len1];
                }
            }
        Arrays.sort(arr);
        int sum=0;
        for(int i=0;i<len1*2;i++){
            sum+=arr[i];
        }
        int target = sum/2;
        TraceBacking(len1,arr,target,0,0);
        return;
    }

    public void TraceBacking(int len,int[] arr,int target,int sum,int startindex){

        if(path.size()==len && Math.abs(target-sum)<min){
             new_A = new ArrayList<>(path);
             return;
        }
        if(path.size()>len)return;

        for(int i=startindex;i<arr.length;i++){
            sum+=arr[i];
            path.add(arr[i]);
            TraceBacking(len,arr,target,sum,i+1);
            path.remove(path.size()-1);
            sum-=arr[i];
        }
        return;
    }
}

[4, 5, 40, 98, 99, 100]
发表于 2021-06-07 16:40:09 回复(0)
感觉应该是正确的,反正试了几种情况感觉效果还好。
/**
 * 解题思路:
 * 先算出两个数组总体的差值,然后分两种情况分析,发现当两个数组总体的差值和
 * A[i]-B[j]的差值的正负值相同的时候交换两个值才有可能会减小总体的差值,
 * 要想能够交换,还需要满足另一个条件就是交换后的总体差值的绝对值应该小于
 * 之前的总体差值的绝对值,这样就可以保证交换后两个数组的差值会减小。
 */
public class ReduceDiff {
    public void mindiff(int[] A,int[] B){
        int diff=0;
        for(int i=0;i<A.length;i++){
            diff+=(A[i]-B[i]);
        }
        for(int i=0;i<A.length;i++){
            for(int j=0;j<B.length;j++){
                int di=A[i]-B[j];
                int newdiff=diff-2*(A[i]-B[j]);
                if(diff*di>0 && Math.abs(newdiff)<Math.abs(diff)){
                    int temp=A[i];
                    A[i]=B[j];
                    B[j]=temp;
                    diff=newdiff;
                }
            }
        }
    }

    public static void main(String[]args){
        int[] aa={100,99,98,1,2, 3};
        int[] bb={34,54,12,1,4,6};
        ReduceDiff reduceDiff=new ReduceDiff();
        reduceDiff.mindiff(aa,bb);

        System.out.println("aa数组为:");
        for(int i :aa){
            System.out.print(i+" ");
        }
        System.out.println("\nbb数组为:");
        for(int i :bb){
            System.out.print(i+" ");
        }

    }
}


发表于 2020-02-18 17:52:21 回复(0)