有两整型数组，如何实现最少次数交换元素，使这两数组元素和的差值最小？
有两整型数组，如何实现最少次数交换元素，使这两数组元素和的差值最小？
如：数组array1={11,2,4,6,7}与数组array2={4,5,8,9,2}，如何最小次数交换它们之间的元素，使array1与array2的元素和的差值最小。
import java.util.Arrays;
/**
?*
?* @author Administrator
?*
?*/
public class TestUtil
{
?private int[] arrysMin = null;
?
?private int[] arrysMax = null;
?
?private int matchNum = 0;
?
?
?/**
? * 返回数组的所有元素的总和
? * @param arrays? 待计算数组
? * @return 所有元素的总和值
? */
?public int getArraySum(int[] arrays)
?{
??int sum = 0;
??if (null != arrays)
??{
???for(int i : arrays)
???{
????sum += i;
???}???
??}
??return sum;
?}
?
?/**
? * 返回数组的差值
? * @param array1 集合一
? * @param array2 集合二
? * @return 差值
? */
?public int getTowArraysMacth(int[] array1,int[] array2)
?{
??Integer l1 = getArraySum(array1);
??Integer l2 = getArraySum(array2);
??
??if ((l1 - l2)/2 > 0)
??{
???arrysMax = array1;
???arrysMin = array2;
???return (l1 - l2)/2;
??}
??else
??{
???arrysMax = array2;
???arrysMin = array1;
???return (l2 - l1)/2;
??}
?}
?
?private boolean isReturn(int[] arrayMax,int[] arrayMin)
?{
??Integer l1 = getArraySum(arrayMax);
??Integer l2 = getArraySum(arrayMin);
??
??if ((l1 - l2) > 0)
??{
???return? false;
??}
??else
??{
???return true;
??}
?}
?
?public void doMatch()
?{
???? //保证大的数组总和永远是大的，以防递归进入死循环
??????? if (isReturn(arrysMax, arrysMin))
??????? {
??????????? return ;
??????? }
??//获取元素总和大的与小的差值平均值
??int match = getTowArraysMacth(arrysMax, arrysMin);
??//使用一个大数字初始化最小绝对值，后面做比较
??int abs = getArraySum(arrysMax);
??int tempElement = 0;
??//最终大数组要交换的下标
??int maxIndex = 0;
??int minIndex = 0;
??if (null != arrysMax && null != arrysMin )
??{
???for (int i=0; i < arrysMax.length; i++)
????? {
????? ?for (int j=0; j < arrysMin.length; j++)
????? ?{
????? ??int temp = arrysMax[i] - arrysMin[j];
????? ??if (temp > 0)
????? ??{
????? ?? //如果元素差值和元素总和大的与小的差值平均值正好相等，直接交换元素OK
????? ??? if (Math.abs(match - temp) == 0)
????? ???{
????? ???? tempElement = arrysMin[j];
????? ???? arrysMin[j] = arrysMax[i];
????? ???? arrysMax[i] = tempElement;
????? ???? matchNum ++;
????? ???? return;
????? ???}
????? ??? else
????? ??? {
????? ???? //否则完全遍历，最终找出元素差值和总和差值平均值差距最小的两元素，
????? ???? if (abs > Math.abs(match - temp))
????? ???? {
????? ????? abs = Math.abs(match - temp);
????? ????? maxIndex = i;
????? ????? minIndex = j;
????? ???? }
????? ??? }
????? ??}
????? ?}
????? }
???? //交换差距最小的两元素
???? tempElement = arrysMin[minIndex];
???? arrysMin[minIndex] = arrysMax[maxIndex];
???? arrysMax[maxIndex] = tempElement;
???
???? //交换次数加加
???? matchNum ++;
???? //递归
???? doMatch();
??}
????
?}
?
?
?public int[] getArrysMin() {
??return arrysMin;
?}
?public void setArrysMin(int[] arrysMin) {
??this.arrysMin = arrysMin;
?}
?public int[] getArrysMax() {
??return arrysMax;
?}
?public void setArrysMax(int[] arrysMax) {
??this.arrysMax = arrysMax;
?}
?public int getMatchNum() {
??return matchNum;
?}
?public void setMatchNum(int matchNum) {
??this.matchNum = matchNum;
?}
?/**
? * @param args
? */
?public static void main(String[] args)
?{
??TestUtil tu = new TestUtil();
??int[] a1 = {11,2,4,6,7};
??int[] a2 = {4,5,8,9,2};
??System.out.println("交换前数组a1：" + Arrays.toString(a1));
??System.out.println("交换前数组a2：" + Arrays.toString(a2));
??//进行第一次分出，两元素的总和谁大谁小
??tu.getTowArraysMacth(a1, a2);
??//开始进行处理交换
??tu.doMatch();
??//打印交换结果
??System.out.println("交换次数：" + tu.getMatchNum());
??System.out.println("a1数组元素和:" + tu.getArraySum(a1) );
??System.out.println("a2数组元素和:" + tu.getArraySum(a2));
??System.out.println("交换后原数组a1:" + Arrays.toString(a1));
??System.out.println("交换后原数组a2:" + Arrays.toString(a2));
?}
}
