3个不同数组的所有元素的总和
3个不同数组的所有元素的总和
提问于 2017-06-03 11:05:21
我希望和优化的算法，以找到每个元素的数组和。
例如，let 3 array：
a = [1,2,3,4];
b = [5,6];
c = [8,9];则最终总和将等于：
sum(1,5,8)+sum(1,5,9)+sum(1,6,8)+sum(1,6,9)+sum(2,5,8)...+sum(4,6,9)
我试过这样做，但我使用的算法的时间复杂度为O(n^3)，所以我想要任何低于这个复杂度的算法。
下面是我的算法：
sum = 0
for(i=0;i<a.size();i++)
for(j=0;j<b.size();j++)
for(k=0;k<c.size();k++)
sum = sum+a[i]+b[j]+c[k];回答 2
Stack Overflow用户
发布于 2017-06-03 11:18:29
在本例中，a、b和c分别有4、2和2个元素。如果您想将它们添加到每种组合中，将会有4 * 2 * 2 = 16术语需要添加。在这些术语中，a的每个元素将出现4次，因为它将被添加到b和c元素的2 * 2 = 4组合中。类似地，b (或c)的每个元素将出现8次，因为它将被添加到a和c (或b)的每个元素的每个4 * 2 = 8组合中。
因此，在最终的和中，a的每个元素将出现4次，b和c的每个元素将出现8次。一旦你弄清楚了，你可以做更少的乘法和加法来得到结果。(只需对单个数组的元素求和，然后将这些和分别乘以4，8和8)。
Stack Overflow用户
发布于 2017-06-03 15:09:02
a的每个元素将与b的每个元素和c的每个元素一起出现在一起。
这意味着a中的每个元素都将以与b.length * c.length相等的数量出现。
这也很容易从蛮力伪代码中看出：(为了可读性进行了修改)
for i = 0 to a.length
for j = 0 to b.length // happens once for each i
for k = 0 to c.length // happens b.length times for each i
sum += a[i] + ... // happens b.length * c.length times for each i概括地说，我们提出了以下算法：
对所有元素求和，将结果与b.length * c.length.
- Sum
-
a相乘，将结果与b.length * c.length.
- Sum all elements
c相乘，将结果与上述三个值相加相乘。
这是一种O(n)算法，其中n是元素的总数或每个数组的平均元素数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44339828
复制相关文章
相似问题
腾讯云开发者
