私は次のようにアルゴリズムを書くように言われました 同じサイズNの3つの配列A []、B []、C []があります。A(i、j、k) [i] + B [j] = C [k]となる。最大許容時間計算量はO(N^2).Following私は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)以上のアルゴリズムですか?
よろしく、 アルカ
可能なすべての(i、j、k)をお探しですか?それとも、トリプルを見つけたいのですか?また、配列のデータは区別されますか? –
あなたのコードは* all *の組み合わせを見つかりません。同じ合計を与える{i、j}のペアが複数ある場合は、それらのうちの1つだけをキャプチャします。 –
また、あなたの現在のソリューションは完全に間違っています。バグが多すぎます。 –