有人告诉我写一个算法如下 共有三个大小为N的数组A[],B[],C[]。找出所有可能的(i,j,k)使得A[i]+B[j]=C[k]。允许的最大时间复杂度是O(N^2)。下面是我写的算法O(N^2)
#include<stdio.h>
#define MAX 1000
struct sum
{
int result;
int i;
int j;
};
int main()
{
struct sum sum_array[MAX];
int n=4;
int a[] = {4,1,2,5};
int b[] = {1,7,6,0};
int c[] = {11,3,8,2};
int k;
int i,j;
for(i=0;i<MAX;i++)
sum_array[i].result=-1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
sum_array[a[i]+b[j]].result=a[i]+b[j];
sum_array[a[i]+b[j]].i=i;
sum_array[a[i]+b[j]].j=j;
}
}
for(k=0;k<n;k++)
{
if(sum_array[c[k]].result==c[k])
{
printf("<i,j,k> = <%d,%d,%d>\n",sum_array[c[k]].i,sum_array[c[k]].j,k);
}
}
return 0;
}
我的问题是如何做得更快?任何 O(N*logN) 或更好的算法吗?
问候, 阿尔卡
最佳答案
最大答案的大小为 N^3,因此无法达到更好的复杂度。 拿这个例子 A={1,1,1,1,1,1,1} , B = {1,1,1,1,1,1} C = {2,2,2,2,2,2您的方法不会为上述示例输出所有可能的三元组。
关于algorithm - 更快的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10044275/