2

有人问我：

用剩余元素的总和替换列表中的每个数字，列表未排序。
所以假设如果我们有一个像 的数字列表{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}

它只需要两次迭代列表。

然后面试官问我：现在不做减法吗？我无法回答:(

其他解决方案可能吗？有人可以分享任何其他技巧吗？有可能有更好的技巧吗？

让我们可以使用额外的内存空间（我试了几分钟后问，即使那样我也无法回答）。

4

6 回答 6

5

一种可能性是计算数组的前缀和后缀总和，然后组合适当的条目。这仍然是 O(n) 但需要更多内存空间，所以我认为您的原始方法更好。

换句话说，从 {2, 7, 1, 3, 8} 计算 {2, 2+7, 2+7+1, 2+7+1+3, 2+7+1+3+8} 和 { 2+7+1+3+8, 7+1+3+8, 1+3+8, 3+8, 8} 然后添加适当的条目。

于 2013-08-19T20:32:32.470 回答
1

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-19T21:16:56.430 回答
1

我想不出比你更好的了。

但是这个怎么样：

创建一个(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-19T20:52:11.197 回答
1

解决方案是将除元素之外的所有内容相加。那么你不必事后减去。您只需跳过在当前索引处添加元素。

或者，您可以获取列表的一个子集，该子集不包括当前索引处的元素，然后将子集相加。与我的第一个建议几乎相同，具有更多实现细节。

于 2013-08-19T20:30:28.143 回答
0 
#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-11T17:41:15.407 回答
-1

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

于 2013-08-19T20:32:42.720 回答