在C中存储数组中的数字

Question

我有三个一维数组.任务是将存在于三个阵列中的每个阵列中的数字存储在第四个阵列中.这是我的解决方案,如你所见,是不正确的.如果可能的话,我也对更快的算法感兴趣,因为它是O(N3)难度.

    #include <stdio.h>
main(){
int a[5]={1,3,6,7,8};
int b[5]={2,5,8,7,3};
int c[5]={4,7,1,3,6};
int i,j,k;
int n=0;
int d[5];
for(k=0; k<5; k++){
    for(j=0; j<5; j++){
        for(i=0; i<5; i++){
            if(a[i]==b[j] && b[j]==c[k])
                {d[n]=a[i];
                n++;}
            else
                d[n]=0;
    }}}
//Iterate over the new array
for(n=0;n<5;n++)
    printf("%d\n",d[n]);
return 0;
}

Answer 1

改进的一种方法O(n log n)是首先对所有三个数组进行排序.然后为每个数组使用三个指针.您总是移动指向最低值的那个,并且在每次这样的移动之后检查三个值是否相同.

为了进一步改进,您可以使用哈希表.迭代第一个数组并将其值作为键放在哈希表中.然后迭代遍历第二个数组,每次当值作为第一个哈希表中的键存在时,将其放在第二个哈希表中.最后迭代第三个数组,如果第二个哈希表中存在一个值作为键存储在第四个数组中.这是O(n)假设哈希表操作O(1).