什么是用于此问题的最佳算法 [英] what is the best algorithm to use for this problem

问题描述

的序列的均衡指数的指数，使得元件中的低指数的总和等于在更高的索引的元素的总和。例如，在一个序列答：

  A [0] =  -  7 A [1] = 1 [2] = 5 A [3] = 2 A [4] =  -  4 A [5] = 3 A [6] = 0
 

3是一个平衡指标，因为：

  A [0] + A [1] + A [2] = A [4] + A [5] + A [6]
 

6也是一个平衡的指标，因为：

  A [0] + A [1] + A [2] + A [3] + A [4] + A [5] = 0
 

（0个元素和为零）7不均衡指数，因为它不是序列A的一个有效索引 如果您还有疑问，这是一个precise定义：整数k是一个序列，当且仅当和

的平衡指标。

假定的零元素的总和等于零。写一个函数

  INT球菌（INT [] A）;
 

这给出的顺序，返回其平衡指数（任何），或-1，如果没有均衡存在索引。假定序列可以是很长的。

解决方案

1. 计算的 A 的所有元素的总和
2. 对于每个指数我，计算元素的总和，从 A [0] 到 A [1 - 1] ，直到总和等于（totalSum - A [1]）/ 2

注意，元素的总和 A [0] 到 A [1 - 1] 可跟踪作为总运行，这意味着整个算法的复杂度是O（n）。为实现code是留给作为练习读者。

Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A. If you still have doubts, this is a precise definition: the integer k is an equilibrium index of a sequence if and only if and .

Assume the sum of zero elements is equal zero. Write a function

int equi(int[] A);

that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long.

解决方案

1. Calculate the total sum of all of the elements in A
2. For every index i, calculate the sum of the elements from A[0] to A[i - 1], until the sum is equal to (totalSum - A[i]) / 2.

Note that the sum of elements from A[0] to A[i - 1] can be tracked as a running total, which means that the complexity of the whole algorithm is O(n). Implementing as code is left as an exercise for the reader.

这篇关于什么是用于此问题的最佳算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！