c++ - 将 vector 的元素与同一 vector 的所有元素相乘

Question

我正在尝试解决一个问题，我想将 vector 的元素与同一 vector 的所有元素相乘(也与自身相乘)。

我有一个可行的解决方案，如下:

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

        }

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

我面临的问题:

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

编辑1:

实际上我想找到数字列表中第 n 个最大的数字，这些数字是通过将 vector 的元素与每个其他元素相乘获得的。 我的方法是:

1. 求乘积并将值存储在 vector 中。 (时间- O(N^2) )。
2. 对 vector 进行排序。 (时间 - O(N logN) )
3. 通过索引访问找到第n大的数。

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

Answer 1

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

input: [a, b, c]

output:

aa ba ca
ab bb cb
ac bc cc

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

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