文档章节

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

pczhangtl
 pczhangtl
发布于 2014/09/01 14:26
字数 391
阅读 35
收藏 0
import java.util.ArrayList;
import java.util.List;

public class LeastSumDiff {
	public static void main(String args[]) {
		int[] a1 = { 100, 99, 98, 1, 2, 3 };
		// int[] a1 = { 40, 50 };
		int[] a2 = { 1, 2, 3, 4, 5, 40 };
		// int[] a2 = { 20, 15 };

//		int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 90, 0, 0, 100 };
//		int a2[] = { -1, -2, -100, -3, 99, -222, -2, -3, -5, -88, 11, 12, 13 };
		//int leastSum = leastSumDiff(a1, a2);
		int leastSum = leastSumDiff1(a1, a2);
		for (int i : a1) {
			System.out.print(i + " ");
		}

		System.out.println();
		for (int i : a2) {
			System.out.print(i + " ");
		}
		System.out.println();
		System.out.println(leastSum);
	}

	public static int leastSumDiff(int[] a1, int[] a2) {
		int leastSum = 0;
		int sumA = 0;
		int sumB = 0;

		for (int i = 0; i < a1.length; i++) {
			sumA += a1[i];
			sumB += a2[i];
		}
		leastSum = Math.abs(sumA - sumB);

		for (int i = 0; i < a1.length; i++) {
			for (int j = 0; j < a2.length; j++) {
				int tmp = sumA + a2[j] - a1[i];
				int tmp1 = sumB + a1[i] - a2[j];
				int tmpLeast = Math.abs(tmp - tmp1);
				if (leastSum > tmpLeast) {
					int tmpa1 = a1[i];
					a1[i] = a2[j];
					a2[j] = tmpa1;
					sumA = tmp;
					sumB = tmp1;
					leastSum = tmpLeast;
					if (tmpLeast == 0) {
						return 0;
					}
				}
			}
		}

		return leastSum;
	}

	// a[i] - b[j] is around (sumA - sumB)/2;
	public static int leastSumDiff1(int[] a, int[] b) {
		int leastSum = 0;
		int sumA = 0;
		int sumB = 0;

		for (int i = 0; i < a.length; i++) {
			sumA += a[i];
			sumB += b[i];
		}
		leastSum = Math.abs(sumA - sumB);

		int nextToLeastSum = leastSum;
		int tmpJ = 0;
		List<Integer> aL = new ArrayList<Integer>();
		List<Integer> bL = new ArrayList<Integer>();
		for (int i = 0; i < a.length; i++) {
			boolean found = false;
			for (int j = 0; j < b.length; j++) {
				int currentGap = Math.abs(a[i] - b[j]) * 2;
				if (leastSum >= Math.abs(a[i] - b[j]) * 2) {
					if (!(leastSum > Math.abs(sumA - a[i] + b[j]
							- (sumB + a[i] - b[j])))) {
						continue;
					}
					if (!found) {
						nextToLeastSum = currentGap;
						tmpJ = j;
						found = true;
					} else {
						if (nextToLeastSum < currentGap) {
							nextToLeastSum = currentGap;
							tmpJ = j;
						}
					}
				}
			}

			if (found) {
				sumA = sumA - a[i] + b[tmpJ];
				sumB = sumB + a[i] - b[tmpJ];
				leastSum = Math.abs(sumA - sumB);
				int tmpa1 = a[i];
				a[i] = b[tmpJ];
				b[tmpJ] = tmpa1;
				nextToLeastSum = leastSum;
			}
			if (leastSum == 0) {
				return 0;
			}
		}

		return leastSum;
	}
}



© 著作权归作者所有

共有 人打赏支持
pczhangtl
粉丝 46
博文 707
码字总数 113318
作品 0
浦东
高级程序员
私信 提问
通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。

题目: 有两个序列 a,b,大小都为 n,序列元素的值任意整数,无序; 要求: 通过交换 a,b 中的元素,使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 例如: var a = [100,99,98,1,2, 3...

Zhang_H
2014/05/18
0
0
十大经典排序算法(动图演示)转

0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 ...

o0无忧亦无怖
2018/07/05
0
0
算法——选择排序、插入排序和希尔排序(改进的插入排序)

选择排序 首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次,在剩下的元素中找到最小的元素,将它与数组的第...

嘿胖丁
2018/03/02
7
0
Leetcode 排序类题目 排序算法总结

1. Merge Sorted Array Description: Easy Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You may assume that nums1 has enough......

BookThief
2018/07/27
0
0
几种排序算法的JAVA语言实现

1、选择排序最差时间复杂度О(n²)最优时间复杂度О(n²)平均时间复杂度О(n²)最差空间复杂度О(n) total, O(1) auxiliary选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理...

奔跑的蛮牛
2013/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

欧拉公式

欧拉公式表达式 欧拉公式的几何意 cosθ + j sinθ 是个复数,实数部分也就是实部为 cosθ ,虚数部分也就是虚部为 j sinθ ,对应复平面单位圆上的一个点。 根据欧拉公式和这个点可以用 复指...

sharelocked
22分钟前
1
0
burpsuite无法抓取https数据包

1.将浏览器和burpsuite的代理都设置好 2.在浏览器地址栏输入: http://burp 3.下载下面的证书,并将证书导入浏览器 cacert.der

Frost729
46分钟前
0
0
JeeSite4.x 消息管理、消息推送、消息提醒

实现统一的消息推送接口,包含PC消息、短信消息、邮件消息、微信消息等,无需让所有开发者了解消息是怎么发送出去的,只需了解消息发送接口即可。 所有推送消息均通过 MsgPushUtils 工具类发...

ThinkGem
今天
6
0
OpenML

https://www.openml.org/search?type=data

shengjuntu
今天
2
0
java强引用,软引用,弱引用和虚引用

先来简要说一下这四种引用的特性: 强引用:如果一个对象具有强引用,那垃圾回收器绝不会回收它 软引用:如果一个对象只具有软引用,则内存空间足够,垃圾回收器就不会回收它 弱引用:在垃圾...

woshixin
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部