/**
* 解题思路:
* 先算出两个数组总体的差值,然后分两种情况分析,发现当两个数组总体的差值和
* 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+" ");
}
}
} 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;
}
}