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