获取数组中每对的产品

Question

我有一个整数数组，我必须找到数组中的每一对产品。 说数组是{1,2,3,4}，那么输出应该是{1*2, 1*3, 1*4, 2*3, 2*4, 3*4}。

除了蛮力之外，还有什么办法可以获得上述结果。通过蛮力我的意思是从数组中取一个数字并循环遍历数组并存储每对数据的产品。这可以做得比O(n^2)更好吗？

Answer 1

如果没有冗余，则除执行n*(n-1)/2乘法之外别无它法。

想象一个图形，其中每个项目是一个节点，每条边代表节点正在连接的乘法。

结果为一个完整图和你的输出是每个边缘的结果，你将有n*(n-1)/2那些。

Answer 2

你不能。因为你可以有O（n^2）独特的结果，你需要O（n^2）操作来访问每个这些数字。

例如，假设2个数组中的所有数字都是唯一的原始数字。