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

pczhangtl

``````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

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

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

2013/12/22
0
0

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

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

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

ThinkGem

6
0
OpenML

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

shengjuntu

2
0
java强引用,软引用，弱引用和虚引用

woshixin

1
0