用列表中的其他数字的总和替换数字不加减

用剩余元素的总和替换列表中的每个数字，列表不被排序。
因此，假设如果我们有一个像{2, 7, 1, 3, 8}这样的数字列表，现在我们要用其余元素的总和替换每个元素。输出应该是：

{(7 + 1 + 3 + 8), (2 + 1 + 3 + 8), (2 + 7 + 3 + 8), (2 + 7 + 1 + 8), (2 + 7 + 1 + 3)} 
== {19, 14, 20, 18, 13}

我回答一个显而易见的解决方案：
首先评估所有的数字sum然后从sum减去每个元素。因此，对于上面所列内容sum是2 + 7 + 1 + 3 + 8 = 21，则输出不喜欢：

{sum - 2, sum - 7, sum - 1, sum - 3, sum - 8} 
    {21 - 2, 21 - 7, 21 - 1, 21 - 3, 21 - 8} 
== {19, 14, 20, 18, 13}

它只需要两次迭代名单。

然后采访者问我：现在没有减法吗？我不能回答:(

是其他的解决方案可能吗？能有的份额任何其他把戏？一个更好的技巧是可能的吗？

让我们可以使用更多的内存空间（我问尝试几分钟后即使这样我也答不上来）。

来源

2013-08-19 Grijesh Chauhan

一种可能性是计算数组的前缀和后缀总和，然后组合适当的条目。这仍然是O（n），但需要更多的内存空间，所以我认为你的原始方法更好。换句话说，从{2,7,1,3,8}计算{2,2 + 7,2 + 7 + 1,2 + 7 + 1 + 3,2 + 7 + 1 + 3 + 8} 8}和{2 + 7 + 1 + 3 + 8,7 + 1 + 3 + 8,1 + 3 + 8,3 + 8,8}，然后添加适当的条目。

来源

2013-08-19 20:32:32

正确的想法，错误的答案。您需要排除该元素，即第一个数组将为{0,2,9,10,13}。然后只需在每个位置添加元素。 – Joel

我同意，你的方式看起来更优雅。 –

*'然后添加适当的条目'*你的意思是在你的两个列表中说A1，A2的输出我应该加上'output [i] = A1 [i] + A2 [N-i]'？请进一步解决。给我更多的时间... –

的解决方案是总结一切但的元素。然后，你不必在事后减去。你只跳过当前索引处添加元素。

或者，你可以得到列表的一个子集，它排除了curren元素t指数，然后将子集合在一起。与我的第一个建议有更多的实现细节几乎一样。

来源

2013-08-19 20:30:28

我告诉他这一点，但我觉得这是没有问题的答案（它太慢了）。 –

@GrijeshChauhan为什么不呢？ –

这最终是'O（n^2）'。 – Teepeemm

-1

而不是减去元素，您可以添加元素乘以-1。我想，乘法和加法是允许的操作。

来源

2013-08-19 20:32:42 phlogratos

这不会给他错误的答案吗？ –

为什么这应该是错误的答案？ 'sum - a'和'sum +（-1 * a）'给出相同的结果，但不使用减法。 – phlogratos

@phlogratos那里Phlogratos那里**必须是**一些其他的解决方案，我一直在想每一个运营商。例如阅读其他答案。我想明白... –

我想不出比你更好的东西。

但是这个怎么样：

创建(n-1)xn矩阵：

[ 2, 7, 1, 3, 8 ] 

| 7, 1, 3, 8, 2 | rotate by 1 
| 1, 3, 8, 2, 7 |   by 2 
| 3, 8, 2, 7, 1 |   by 3 
| 8, 2, 7, 1, 3 |   by 4

再总结列

C++的std::rotate_copy可以用来创建矩阵

std::vector<int> v1 {2, 7, 1, 3, 8 }; 
    std::vector<int> v2 (v1.size()); 
    int i,j; 

    std::vector< std::vector<int> > mat; 
    for (int i=1; i<v1.size();++i){ 
    std::rotate_copy(v1.begin(),v1.begin()+i,v1.end(),v2.begin()); 
    mat.push_back(v2); 
    }            

    for(j=0;j<v1.size();++j) 
    for(i=0;i<v1.size()-2;++i) 
     v2[j]+=mat[i][j]; 

for(i=0;i<v2.size();++i) 
    std::cout<<v2[i]<<" ";

来源

2013-08-19 20:52:11 P0W

POW这是其他元素的总和，我认为问题（不是答案）内存+迭代都需要更多:( –

如果时间和空间复杂性无关紧要，这确实限定了不减法的限制。 – Kunal

C++实现。 O（n）并通过在某个索引之前和之后保留所有元素的总和来完成。

#include <iostream> 

int main() { 
    int a[] = {2,7,1,3,8}; 

    int prefix[5]; // Sum of all values before current index 
    int suffix[5]; // Sum of all values after current index 

    prefix[0] = 0; 
    suffix[4] = 0; 

    for(int i = 1; i < 5; i++) { 
     prefix[i] = prefix[i-1] + a[i-1]; 
     suffix[4 - i] = suffix[4 - i + 1] + a[4 - i + 1]; 
    } 

    // Print result 
    for (int i = 0; i < 5; i++) { 
     std::cout << prefix[i] + suffix[i] << " "; 
    } 
    std::cout << std::endl; 
}

来源

2013-08-19 21:16:56 PherricOxide

#include <iostream.h> 
#include <stdio.h> 

int main() { 
    int a[] = {2,7,1,3,8}; 

    int sum[5]={0}; 


    for(int j = 0; j < 5; j++){ 
     for(int i = 1; i < 5; i++) { 
     sum[j]=sum[j]+a[(j+i+5)%5]; 
     } 
     printf("%d ", sum[j]); } 
}

来源

2013-12-11 17:41:15 abhinav

用列表中的其他数字的总和替换数字不加减

回答

相关问题