如何高效计算一个大小按算术序列排列的数组部分的总和?

huangapple go评论79阅读模式
英文:

How can I efficiently compute the sum of parts of an array of sizes in an arithmetic sequence?

问题

我试图找出给定数组的部分和,其长度是前N个正整数的总和,其中N是某个整数。我需要找出要求和的每个部分的大小,这些部分的大小是所述等差数列中的数字。例如,对于长度为10的数组,我需要找出第一个数字的和,接下来的两个数字的和,依此类推,直到下一个N个数字。

示例输入:

[1,4,5,2,6,7,9,8,7,10]

示例输出:

[1,9,15,34]//1, 4+5, 2+6+7, 9+8+7+10

解释:

第一个和是1,即第一个元素(索引0)。接下来两个数字的和是4 + 5 = 9(索引1和2)。接下来三个数字的和是2 + 6 + 7 = 15(索引3, 4, 和5)。最后四个数字的和是9 + 8 + 7 + 10 = 34(索引6, 7, 8, 和9)。

英文:

I am trying to find the sum of parts of a given array with a length that is the sum of the first N positive integers for some whole number N. The size of each part for which I am to find the sum are the numbers in said arithmetic sequence. For instance, for an array of length 10, I need to find the sum of the first number, the next two numbers, and so on, until the next N numbers.

Example Input:

[1,4,5,2,6,7,9,8,7,10]

Example Output:

[1,9,15,34]//1, 4+5, 2+6+7, 9+8+7+10

Explanation:

The first sum is 1, the first element (index 0). The sum of the next two numbers is 4 + 5 = 9 (index 1 and 2). The sum of the next three numbers is 2 + 6 + 7 = 15 (index 3, 4, and 5). The sum of the last four numbers is 9 + 8 + 7 + 10 = 34 (index 6, 7, 8, 9).

答案1

得分: 0

你可以使用算术序列求和的公式来计算结果数组的大小,即 n(n + 1) / 2

这里可以应用前缀和数组,以便在 O(1) 时间内计算任何范围的和,预先计算时间和空间复杂度为 O(n)(这也是此算法的总体复杂度)。

final int[] input = { 1, 4, 5, 2, 6, 7, 9, 8, 7, 10 };
// size * (size + 1) / 2 = input.length
final int size = (-1 + (int) Math.sqrt(1 + 8 * input.length)) / 2;
// 由二次方程推导而来
final int[] result = new int[size];
final int[] sum = new int[input.length + 1];
for (int i = 1; i <= input.length; i++) {
    sum[i] = sum[i - 1] + input[i - 1];
}
for (int i = 1, j = 0; i <= input.length; i += ++j) {
    result[j] = sum[i + j] - sum[i - 1];
}
System.out.println(Arrays.toString(result));

Ideone Demo

英文:

You can compute the size of the result array using the formula for the sum of an arithmetic sequence, i.e. n(n + 1) / 2.

A prefix sum array can be applied here so so that any range sum can be computed in O(1) time with O(n) precomputation time and space (which is also the overall complexity of this algorithm).

final int[] input = { 1, 4, 5, 2, 6, 7, 9, 8, 7, 10 };
// size * (size + 1) / 2 = input.length
final int size = (-1 + (int) Math.sqrt(1 + 8 * input.length)) / 2;
// derived by quadratic formula
final int[] result = new int[size];
final int[] sum = new int[input.length + 1];
for (int i = 1; i &lt;= input.length; i++) {
    sum[i] = sum[i - 1] + input[i - 1];
}
for (int i = 1, j = 0; i &lt;= input.length; i += ++j) {
    result[j] = sum[i + j] - sum[i - 1];
}
System.out.println(Arrays.toString(result));

<kbd>Ideone Demo</kbd>

答案2

得分: 0

以下是已翻译的内容:

以下算法非常高效,不依赖于求和公式(正如您所要求的),只用来计算结果数组的长度。这不应该是问题,因为它是基本代数。如果您使用了List的实现,您就不必这样做。

它也只对给定数组允许的最大值求和。所以如果您提供了一个数组如下:

1 2 3 4 5 6 7 8 9 10 11 12 13

它将静默地忽略111213,因为它们不包含足够的值以继续。

以下是使用您的原始数据集和输出的算法。

int[] arr = { 1, 4, 5, 2, 6, 7, 9, 8, 7, 10 };

int start = 0; // 组的起始
int end = 0; // 组的结束
int[] sol = new int[(int)(-.5 + Math.sqrt(2*arr.length + .25))];
for (int i = 1; i &lt;= sol.length; i++) {
    // 初始化和
	int sum = 0;
    // 计算下一个结束位置
	end += i;
    // 并从起始位置到结束位置求和
	for (int k = start; k &lt; end; k++) {
		sum += arr[k];
	}
    // 旧的结束位置变为下一个起始位置
	start = end;

    sol[i-1] = sum;
}

打印结果:

[1, 9, 15, 34]
英文:

The following algorithm is very efficient and does not rely on the summation formula to work (as you had asked about) other than to compute the length of the result array. This should not be a problem since it is basic algebra. If you use a List implementation you would not have to do that.

It also only sums only to the max allowed by the given array. So if you provide an array like

1 2 3 4 5 6 7 8 9 10 11 12 13

It will silently ignore 11 12 and 13 since they don't comprise enough values to continue.

Here is the algorithm with your original data set and the output.

		
int[] arr = { 1, 4, 5, 2, 6, 7, 9, 8, 7, 10 };

int start = 0; // start of group
int end = 0; // end of group
int[] sol = new int[(int)(-.5 + Math.sqrt(2*arr.length + .25))];
for (int i = 1; i &lt;= sol.length; i++) {
    // initialize the sum
	int sum = 0;
    // compute next end
	end += i;
    // and sum from start to end
	for (int k = start; k &lt; end; k++) {
		sum += arr[k];
	}
    // old end becomes next start
	start = end;

    sol[i-1] = sum;
}

Prints

[1, 9, 15, 34]


</details>



huangapple
  • 本文由 发表于 2020年8月14日 07:56:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/63404726.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定