我在解决这个问题时遇到了一些问题:
给定一个数组 int
s、 将输入分成两组,使其总和尽可能接近,两组长度必须相等,或者如果输入长度为奇数,则一组可以比另一组多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;
}
2条答案
按热度按时间fafcakar1#
这是不对的。
不管其他答案中提到的一堆小的编码错误,您的算法都不起作用。
考虑输入
[3, 3, 2, 2, 2]
. 你的算法会把它分成[3, 2, 2]
以及[3, 2]
差一点7-5=2
. 但是,存在一个更好的等额分割:[3, 3]
以及[2, 2, 2]
.我不会提供一个完整的算法,但会给你一些提示:
1-最小差值可以进行二进制搜索。如果你能想出一个算法来决定是否有可能拆分数组,这样子的和的差就最多了
d
对于给定的d
,则可以对最小值进行二进制搜索d
算法输出的1
.2-看看子集和问题,它可以帮助解决我在第1项中定义的子问题。
hk8txs482#
在分析并运行了你的代码之后,我做了3个观察。
代码中有很多小错误。
第4行(“dif”初始化)第11行(“for”关键字)出现语法错误
第26行第27行出现逻辑错误(必须访问索引“x”,而不是访问索引“i”)
第17行出现运行时错误(正在初始化
x=list.size()
将引发运行时错误java.lang.IndexOutOfBoundsException
)不过,重要的事情要看,下面提到
这是一个建议,如果您不使用“sum1”和“sum2”打印列表,那么创建和操作另外两个输出列表是多余的。在遍历主列表时,可以计算列表的各个总和。
最重要的是,在遍历列表然后对它们进行除法之后计算sum1和sum2的方法是不可靠的。下列输入将产生意外的输出
[4,6,45,3,2,5,10]
. 因此,我建议您使用最可靠的方法来计算列表1和列表2的总和,即在遍历列表时计算它们(您还可以删除bigSum
)最后一句话:试着自己实现上面提到的想法。