问题描述
因此,我试图将int数组拆分为两个数组,以使数组总和之差最小.有谁知道我该怎么办?或任何提示?
So I'm trying to split int array into two arrays that the difference of arrays sums would be minimum. Does anyone have any ideas how can I do that? Or any tips?
F.e. int [] S = {1,1,3,6};
我们可以将 S
数组拆分为
int[] a = {1,1,3};
和
int [] b = {6};
数组 a
的总和为5,而数组 b
的总和为6,因此最小差为1.> S ,例如 a
和 b
,而不是总和.
Array a
sum is 5 and array b
sum is 6 so the minimum difference is 1. By the way, I'm trying to get split arrays of S
like a
and b
, not the sums difference.
输入: int [] S = {1,1,3,6};
输出: int [] a = {1,1,3};
和 int [] b = {6};
.那就是我想要做的.
Output: int[] a = {1,1,3};
and int[] b = {6};
. That's what I'm trying to do.
到目前为止,我已经尝试过链接
So far I've tried Link
问题已解决!谢谢大家的帮助!
推荐答案
链接与您展示给我们的问题相比,您提出的问题更复杂.在您的示例中,不能对元素进行重新排序",因此只能将数组分为两部分.您只需要选择剪切"的位置即可.
The link you gave is for a more complex problem than the one you are showing us. In your example, elements can't be "reordered", so you can only subdivide the array in two parts. You simply have to choose where to "cut".
var array = new int[] { 1, 1, 3, 6 };
int leftSum = 0;
int rightSum = 0;
for (int i = 0; i < array.Length; i++)
{
rightSum += array[i];
}
int leftArraySize = 0;
int minDiff = rightSum;
for (int i = 0; i < array.Length; i++)
{
rightSum -= array[i];
leftSum += array[i];
int diff = Math.Abs(rightSum - leftSum);
if (diff < minDiff)
{
minDiff = diff;
leftArraySize = i + 1;
}
}
var leftArray = new int[leftArraySize];
var rightArray = new int[array.Length - leftArraySize];
Array.Copy(array, 0, leftArray, 0, leftArray.Length);
Array.Copy(array, leftArray.Length, rightArray, 0, rightArray.Length);
没有Linq的简单代码:您有两个和池", leftSum
和 rightSum
.您对 rightSum
池中的数组的所有元素求和.然后逐个元素地将一个元素从 rightSum
和移动"到 leftSum
和.然后,您检查两个和池"之间的差异是否最小.然后,您只需将元素复制到两个新数组中即可.
Simple code, without Linq: you have two "sum pools", leftSum
and rightSum
. You sum all the elements of the array in the rightSum
pool. Then element by element you "move" one element from the rightSum
sum to the leftSum
sum. You then check if/when the difference between two "sum pools" is the minimum one. Then you simply copy the elements in two new arrays.
这篇关于将int数组拆分为两个数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!