给定序列的平衡指数:找到一个序列的最佳算法是什么? [英] Equilibrium index of a given sequence: What is the best algorithm to find one?

问题描述

序列的平衡索引是这样的索引，即较低索引处的元素之和等于较高索引处的元素之和.例如，按顺序A:

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是一个平衡指数，因为:

3 is an equilibrium index, because:

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

6也是一个平衡指数，因为:

6 is also an equilibrium index, because:

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

(零个元素的总和为零)7不是均衡索引，因为它不是序列A的有效索引.如果您仍然有疑问，这是一个精确的定义:当且仅当和时，整数k是序列的平衡指数.

(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);

给定一个序列，则返回其平衡指数(任意)；如果不存在平衡指数，则返回-1.假设序列可能很长.

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. 计算 A
中所有元素的总和
2. 对于每个索引 i ，计算从 A [0] 到 A [i-1] 的元素之和，直到sum等于(totalSum-A [i])/2 .

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.

请注意，可以跟踪从 A [0] 到 A [i-1] 的元素总和，这意味着操作的复杂性整个算法为O(n).留给读者练习是作为代码实现.

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屋！