獲取數組中每對的產品

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個數組中的所有數字都是唯一的原始數字。