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;
}
}
分享到:
相关推荐
可以把它用于分布式应用之间的数据通信或者异构环境下的数据交换。作为一种效率和兼容性都很优秀的二进制数据传输格式,可以用于诸如网络传输、配置文件、数据存储等诸多领域。 压缩包中包括如下文件: protobuf-all-...
因此XML常用于数据交换、对象序列化(这种序列化和Java对象的序列化技术有着本质的区别)。 Stream对象相当Java对象和XML之间的转换器,转换过程是双向的。创建XSteam对象的方式很简单,只需要new XStream()即可。...
protobuf是谷歌定义的一种语言无关、平台无关的数据交换格式,可以将对象序列化为字节数组、将字节数组反序列化为对象。
可以把它用于分布式应用之间的数据通信或者异构环境下的数据交换。作为一种效率和兼容性都很优秀的二进制数据传输格式,可以用于诸如网络传输、配置文件、数据存储等诸多领域。 压缩包中包括如下文件: protobuf-all-...
可以把它用于分布式应用之间的数据通信或者异构环境下的数据交换。作为一种效率和兼容性都很优秀的二进制数据传输格式,可以用于诸如网络传输、配置文件、数据存储等诸多领域。 压缩包中包括如下文件: java库 ...
google 提供了多种语言的实现:java、c#、c++、go 和 python,每一种实现都包含了相应语言的编译器以及库文件。由于它是一种二进制的格式,比使用 xml 进行数据交换快许多。可以把它用于分布式应用之间的数据通信...
1、远程通讯:提供对多种基于长连接的NIO框架抽象封装,包括多种线程模型,序列化,以及“请求-响应”模式的信息交换方式; 2、集群容错:提供基于接口方法的透明远程过程调用,包括多协议支持,以及软负载均衡,...
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 HttpAsyncClient HttpAsyncClient 是一个异步的 HTTP 客户端开发包,基于 HttpCore NIO 和 HttpClient ...
题目:利用条件运算符的嵌套来完成此题:学习成绩>=90分的同学用A表示,60-89分之间的用B表示,60分以下的用C表示。 1.程序分析:(a>b)?a:b这是条件运算符的基本例子。 【程序6】 题目:输入两个正整数m和n,求...
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 HttpAsyncClient HttpAsyncClient 是一个异步的 HTTP 客户端开发包,基于 HttpCore NIO 和 HttpClient ...
getMaxElem.java 获取数组中的最大元素 incCapicity.java 演示StingBuffer的容量增长 SortDemo.java 排序示例 travelTwoDime.java 遍历二维数组 traversing.java 遍历一维数组 useStrBuf.java 使用...
Google Protocol Buffer( 简称 Protobuf) 是 Google 公司内部的混合语言数据标准,目前已经正在使用的有超过 48,162 种报文格式定义和超过 12,183 个 .proto 文件。他们用于 RPC 系统和持续数据存储系统。 Protocol...
7.5.2 其他字符集与Unicode字符集之间的转换... 173 7.5.3 如何使用其他字符集编写XML. 174 7.6 本章小结... 176 第二部分 文档类型定义... 177 第8章 文档类型定义和合法性... 177 8.1 文档类型定义... 177 ...
冒泡排序是一种简单的排序算法,它的基本思想是通过相邻元素之间的比较和交换,将待排序序列中的最大元素逐步沉底,直到整个序列有序为止。冒泡排序的时间复杂度为O(n^2),其中n为待排序序列的长度。 冒泡排序的...
Gson是Google提供的用来在Java对象和JSON数据之间进行映射的Java类库。可以将一个JSON字符串转成一个Java对象(反序列化),或者反过来(序列化)。 GSON地址:google/gson (github.com) Android引入GSON: ...
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 HttpAsyncClient HttpAsyncClient 是一个异步的 HTTP 客户端开发包,基于 HttpCore NIO 和 HttpClient ...
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 HttpAsyncClient HttpAsyncClient 是一个异步的 HTTP 客户端开发包,基于 HttpCore NIO 和 HttpClient ...
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 HttpAsyncClient HttpAsyncClient 是一个异步的 HTTP 客户端开发包,基于 HttpCore NIO 和 HttpClient ...
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。 异步HTTP客户端开发包 HttpAsyncClient HttpAsyncClient 是一个异步的 HTTP 客户端开发包,基于 HttpCore NIO 和 HttpClient ...