将向量的元素与同一向量的所有元素相乘

Question

我正在尝试解决一个问题，我想将向量的元素与同一向量的所有元素相乘（也与自身相乘）。

我有一个可行的解决方案，如下所示：

for(int i=0;i<v.size();i++)
        {
            for(int j=0;j<v.size();j++)
            {
                r.insert(v[i]*v[j]);
            }

        }

这里，v 是我最初存储元素的向量，r 是我存储产品的向量。

我面临的问题:

这是一个 O(N^2) 算法，我想在 O(N) 时间内实现。有什么办法可以做到这一点？谢谢

编辑 1：

实际上我想在通过将向量的元素与所有其他元素相乘而获得的数字列表中找到第 n 个最大的数字。我的方法是：

求乘积并将值存储在向量中。（时间- O(N^2) ）。
对矢量进行排序。（时间 - O（N logN））
通过索引访问找到第n大数。

我想提高N^2的时间复杂度。

Answer 1

这个问题在当前公式中无法在 O(n) 时间内解决，因为输出有 O(n^2) 个元素。

Answer 2

您可以做的是避免两次计算相同的值。事实上，使用您的解决方案，所有对都将乘以两次。如果您在矩阵中显示结果值，效果最好：

input: [a, b, c]

output:

aa ba ca
ab bb cb
ac bc cc

你可以看到对角线两边的对称性。这意味着当计算第 n 列时，您只需要计算 size of input - n 值，因为其他 n 已经存在于前面的列中，您可以在其中检索它们。

请注意，这不会影响算法的复杂性。

将向量的元素与同一向量的所有元素相乘

Multiply elements of a vector with all elements of same vector

c++

vector