我正在尝试解决一个问题,给定一个整数数组,我需要找到所有可能的元素对之和。例如,数组为1,2,3,4,则结果应该是1+2 + 1+3 + 1+4 + 2+3 + 2+4 + 3+4 = 30。
我尝试了不同的方法,但是没有想出复杂度低于O(n^2)的算法。请问是否有任何关于复杂度低于O(n^2)的算法?
我尝试了不同的方法,但是没有想出复杂度低于O(n^2)的算法。请问是否有任何关于复杂度低于O(n^2)的算法?
n-1
对中,因此将它们全部相加并乘以 n-1
,即为 O(n)
。
k
元多重集合和的情况。在这种情况下,数组中的每个元素都恰好出现在 (n-1) 选择 (k-1)
个多重集中,因此将它们全部相加并乘以该值。计算二项式系数可能会有点困难,但绝对比枚举所有 k
元多重集并将它们相加要好。除非您对数组中的值有所了解,否则我看不到任何不是O(n^2)的方法可以做到这一点。
N个物品取2个的组合数为:
N C
10 45
100 4950
1000 499500
正如您所看到的,组合数量约为(N^2)/2,因此我不认为在没有额外信息的情况下您能做得更好。
next_permutation()
的函数,它可以生成数组中下一个元素的“组合”。因此,您可以像这样做:int A=[1,2,3,4,5];
while(next_permutation(A,A+5)) //NOTE: A is pointer to first element of array A
{
// do something
}