我在解决这个问题时遇到了一些问题:
给定一个 int
数组,将输入分成 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]
和 [3, 2]
,相差 7-5=2
。但是,存在一个更好的相等总和拆分:[3, 3]
和 [2, 2, 2]
。
我不会提供一个完整的算法,但会给你一些提示:
1 - 可以对最小差异进行二进制搜索。如果你能想出一个算法来决定是否可以拆分数组,使得对于给定的 d
,各部分之和的差最多为 d
, 然后你可以二进制搜索算法输出 1
的最小 d
。
2 - 查看 subset sum problem ,它可以帮助解决我在第 1 项中定义的子问题。
关于java - java中2组的最接近和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65494960/