我在解决这个问题时遇到一些问题:
给定一个数组int
s,将输入分为 2 组,使其总和尽可能接近,2 组的长度必须相等,或者如果输入是奇数长度,则一组可以比另一组多 1。然后先打印较低的总和,然后打印较高的总和。
前任:
输入->[4,6,17,3,2,5,10]
输出->23,24 ([17,5,2] , [10,6,4,3])
这是我想出的,到目前为止我已经测试过它已经通过,但我不知道它是否真的正确:
public static String closestSums(int[] input) {
Integer sum1 = 0;
Integer sum2 = 0;
Integer dif = 0;
Integer bigSum = 0;
List<Integer> list = new ArrayList<>();
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
for (int x = 0; x < input.length; x++) {
list.add(input[x]);
}
Collections.sort(list);
for (int x = list.size(); x >= 0; x--) {
bigSum += list.get(x);
if (dif == 0) {
dif = list.get(x);
list2.add(list.get(x));
}
else if (dif > 0) {
dif -= list.get(x);
list1.add(list.get(x));
}
else {
dif += list.get(x);
list2.add(list.get(x));
}
}
dif = Math.abs(dif);
if (dif != 0) {
sum2 = (bigSum / 2) + dif;
sum1 = bigSum / 2;
}
else {
sum2 = bigSum / 2;
sum1 = bigSum / 2;
}
return sum1 + ", " + sum2;
}
这是不正确的。
不管其他答案中提到的一堆小编码错误,你的算法都不起作用。
考虑输入[3, 3, 2, 2, 2]
。你的算法会将其分为[3, 2, 2]
and [3, 2]
差异为7-5=2
。然而,存在更好的等总分割:[3, 3]
and [2, 2, 2]
.
我不会提供完整的算法,但会给您一些提示:
1 - 最小差异可以进行二分查找。如果你能想出一个算法来决定是否可以分割数组,使得各部分之和的差值最多为d
对于给定的d
,那么你可以二分查找最小的d
算法输出的1
.
2 - 看子集和问题 https://en.wikipedia.org/wiki/Subset_sum_problem,它可以帮助解决我在第 1 项中定义的子问题。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)