当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-32.通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小(两数组的差最小)。

发表于: 2012-01-18   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; public class MinSumASumB { /** * Q32.有两个序列a,b,大小都为n,序列元素的值任意整数,无序. * * 要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。 * 例如: * int[] a = {100,99,98,1,2,3
import java.util.Arrays;

public class MinSumASumB {

	/**
	 * Q32.有两个序列a,b,大小都为n,序列元素的值任意整数,无序.
	 * 
	 * 要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。 
	 * 例如: 
	 * int[] a = {100,99,98,1,2,3}; 
	 * int[] b = {1, 2, 3, 4,5,40};
	 * 
	 * 求解思路: 
	 * 当前数组a和数组b的和之差为 A = sum(a) - sum(b) a的第i个元素和b的第j个元素交换后,
	 * a和b的和之差为 A' 
	 * =sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i]) 
	 * = sum(a) - sum(b) - 2 (a[i] -b[j]) 
	 * = A - 2 (a[i] - b[j]) 
	 * 设x = a[i] - b[j], 则交换后差值变为 A’ = A - 2x
	 * 
	 * 假设A > 0, 当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,
	 * 如果找不到在(0,A)之间的x,则当前的a和b就是答案。 所以算法大概如下:
	 * 在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,
	 * 重复前面的步骤直至找不到(0,A)之间的x为止。
	 */
	public static void main(String[] args) {
		MinSumASumB minSumASumB=new MinSumASumB();
		//int[] a = {100,99,98,1,2,3}; 
		//int[] b = {1, 2, 3, 4,5,40};
		//int[] a={3,5,10};
		//int[] b={20,25,50};
		int[] a={3,5,-10};
		int[] b={20,25,50};
		minSumASumB.swapToMinusDiff(a, b);
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(b));
	}

	public void swapToMinusDiff(int[] a,int[] b){
		
		int sumA=sum(a);
		int sumB=sum(b);
		
		if(sumA==sumB)return;
		
		if(sumA<sumB){
			int[] temp=a;
			a=b;
			b=temp;
		}
		int curDiff=1;
		int oldDiff=Integer.MAX_VALUE;
		int pA=-1;
		int pB=-1;
		boolean shift=true;
		int len=a.length;//the length of a and b should be the same
		while(shift&&curDiff>0){
			shift=false;
			curDiff=sum(a)-sum(b);
			for(int i=0;i<len;i++){
				for(int j=0;j<len;j++){
					int temp=a[i]-b[j];
					int newDiff=Math.abs(curDiff-2*temp);
					if(newDiff<curDiff&&newDiff<oldDiff){
						shift=true;
						oldDiff=newDiff;
						pA=i;
						pB=j;
					}
				}
			}
			if(shift){
				int temp=a[pA];
				a[pA]=b[pB];
				b[pB]=temp;
			}
		}
		System.out.println("the min diff is "+oldDiff);
	}
	public int sum(int[] a){
		int sum=0;
		for(int each:a){
			sum+=each;
		}
		return sum;
	}
}

java-32.通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小(两数组的差最小)。

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
/* * Copyright (c) 2014, 烟台大学计算机学院 * All rights reserved. * 作 者:王颖 * 完成日期:
计算序列中元素的位置 寻找序列中元素的位置,这里序列是有序的。根据序列中元素是否有重复分为无重
#include <iostream> #include <cstdlib> #include <vector> using namespace st
题目要求:   把一个不降序数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一
/* This is a free Program, You can modify or redistribute it under the terms of GNU *Descript
#include "stdafx.h" #include <iostream> using namespace std; //定义结点类型 struct Node
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
新手发帖,很多方面都是刚入门,有错误的地方请大家见谅,欢迎批评指正 一、题外话 上一节学了Pytho
/* * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved. * 作 者: 刘同宾 * 完成日
/* * 程序的版权和版本声明部分: * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号