算法code优化：查找Equilibirum：查找数组的索引，使得其preFIX总和等于其后缀总和 [英] Algorithm Code Optimization: Find the Equilibirum: Find an index in an array such that its prefix sum equals its suffix sum

问题描述

这是我的任务描述：

一个零索引数组A由N个整数的给出。

A zero-indexed array A consisting of N integers is given.

此阵的平衡指数为任何整数p 0≤P＆LT; N和较低的指数的元素的总和等于较高指数，即元素的总和
A [0] + A 1 + ... + A [P-1] = A [P + 1] + ... + A [N-2] + A [N-1]。

An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e. A[0] + A1 + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

零元素的总和被假定为等于0。这可能发生，如果P = 0，或者如果P = N-1。
例如，请考虑以下数组A由N = 8的元素：

Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1. For example, consider the following array A consisting of N = 8 elements:

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

P = 1 is an equilibrium index of this array, because:
•   A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
•   A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
•   A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0

和有与指数大于7的任何元素。
    P = 8不是平衡索引，因为它不符合条件0≤P＆下; ñ。

and there are no elements with indices greater than 7. P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

写一个函数：
INT溶液（NSMutableArray的* A）;
，给定一个零索引数组A由N个整数的，任何返回其平衡指数。

Write a function: int solution(NSMutableArray *A); that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices.

函数应该返回-1，如果没有平衡指数存在。
例如，给定阵列上方A中所示，函数可以返回1,3或7，如上所述

The function should return −1 if no equilibrium index exists. For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

假设：
    •N是范围[0..100,000]内的整数;
    •数组A中的每个元素在该范围内的整数。[-2,147,483,648..2,147,483,647]

Assume that: • N is an integer within the range [0..100,000]; • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

复杂性：
    •预计最坏情况下的时间复杂度为O（N）;
    •预计最坏情况下的空间复杂度为O（N），超越输入存储（不包括对输入参数所需的存储空间）。

Complexity: • expected worst-case time complexity is O(N); • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

输入数组的元素可以被修改。

Elements of input arrays can be modified.

这是我的目标C的问题解决方法：的

Here's my Solution for the problem in Objective C:

-(int)solution:(NSArray *) A{
for (int i=0; i<A.count; i++) {

    NSUInteger backwardsTotal = 0;
    if (i > 0) {
        for (int k=0; k<i; k++) {
            NSNumber *kValue = A[k];
            backwardsTotal += kValue.intValue;
        }
    }

    NSUInteger forwardTotal = 0;
    for (int j=i+1; j<A.count; j++) {
        NSNumber *jValue = A[j];
        forwardTotal += jValue.intValue;
    }

    if (backwardsTotal == forwardTotal) {
        return i;
    }
}

return -1;
}

如何优化这一解决方案？

How can i optimise this solution?

该方法，在每@Nikki评论的变化：

Changes made to the method as per @Nikki comments:

-(int)solution:(NSArray *) A{
NSUInteger a = 0, b = 0;

for (int i=0; i<A.count; i++) {
    NSNumber *iValue = A[i];
    b += iValue.intValue;
}
NSLog(@"Total: b: %ld", b);

for (int k=0; k<A.count; k++) {
    NSNumber *kValue = A[k];
    b -= kValue.intValue;

    NSLog(@"b: %ld", b);
    NSLog(@"a: %ld", a);

    if (a == b)
        return k;

    a += kValue.intValue;

}

return -1;
}

我测试上述code如下：

I am testing the above code as follows:

//    NSArray *array = @[@"-3", @"0", @"3"];
NSArray *array = @[@"-2", @"4", @"-5", @"6", @"1", @"-6", @"2", @"1"];
NSUInteger one = [self solution:array];
NSLog(@"one: %ld", one);//returns 7

解决方案似乎更好地工作。
但是，它仍然是不完美的，并且使用O（N ** 2）的时间复杂度。
而且还有其他性能测试超时错误。

The solution seems to work better. But still, it is not perfect and uses O(N**2) time complexity. And also there are Timeout errors in other Performance tests.

下面截图：

这能仍然优化？

推荐答案

您当前的解决方案是O（n ^ 2）操作（您总结全阵列式n次）。

Your current solution is O(n^2) operations (You sum the whole array n times).

您可以在任何点上，a和b仅2变量设定为零和b到阵列的总和。随后，遍历所有的指标。当通过迭代指数I，首先做B - =改编[1]。然后，如果一个== B，返回岛然后做一个+ =改编[1]。那是O（n）的操作，更加高效。

You could have just 2 variables at any point, a and b, setting a to zero and b to the sum of the array. Afterwards, iterate over all of the indices. When iterating over index i, first do b -= arr[i]. Then, if a==b, return i. Then do a += arr[i]. That is O(n) operations, much more efficient.

这篇关于算法code优化：查找Equilibirum：查找数组的索引，使得其preFIX总和等于其后缀总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！