汇总整数数组的最有效方法

问题描述

我正在尝试找到一个sub- O(n)方法来计算整数数组的总和~~~(而不是遍历 0-n ，我正在 n/2 中进行操作)~~~ 我仍在O(n)中进行操作.

I am trying to find a sub-O(n) method to calculate the sum of an integer array ~~~(instead of iterating through 0 - n, I am doing it in n/2)~~~ I'm still doing it in O(n).

public static int sum(int[] s) {
    int length = s.length - 1;
    int half = length/2;
    int sum = 0;
    for(int i = 0; i <= half; i++) {
        System.out.println(i + " " + s[i] + " + " + s[length - i]);
        sum += s[i] + s[length - i];
    }
    return sum;
}

我的算法适用于偶数个整数，但是，当存在奇数个整数时，它将对中间索引求和两次:

My algorithm works for even number of integers, however, when there are odd number of integers, it would sum the middle index twice:

测试:

    int[] arr = {1, 2, 3, 4, 5};
    System.out.println(sum(arr));

输出:

0 1 + 5
1 2 + 4
2 3 + 3
Sum: 18

我的问题是-求中间数字奇数索引的最佳方法是什么?

My question is - what is the best way to sum up the middle index for odd-number of numbers?

推荐答案

即使您在一天结束时从0变为n/2，也仍然是O(n)，您要触摸数组的每个元素至少一个时间.要对整数数组求和至少可以做的是O(n)，因为您必须触摸数组中的每个元素一次才能将其包括在总和中.

That's still O(n) even if you go from 0 to n/2 at the end of the day you are touching every element of the array at least one time. And to sum up an array of integers the least you can do is O(n) because you have to touch every element in the array one time to include it in the sum.

这篇关于汇总整数数组的最有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！