Storing numbers in array in C

I have three o开发者_高级运维ne-dimensional arrays. The task is to store the numbers which exist in each of the three arrays in a forth array. Here is my solution which as you see isn't correct. I'm also interested in a faster algorithm if possible because it's O(N3) difficulty.

    #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;
}

One way to improve to O(n log n) is to sort all three arrays first. Then use three pointers one for each array. You always move the one that points to the lowest value and after every such move check whether the three values are the same.

To improve even further you can use hashtable. Iterate through the first array and put it's values in a hashtable as keys. Then iterate through the second array and every time when the value exists as a key in the first hashtable, put it in a second one. Finally iterate over the third array and if a value exists in the second hashtable as a key store it in the forth array. This is O(n) assuming the hashtable operations are O(1).

Your mistake is that you're using one of your three nested counters (which are being used to index the input arrays) as the index into the output array. You need to have a fourth index (let's call it n), which starts at zero, only increments every time a satisfactory value has been found.

Sort second and third arrays beforehand and use binary search on them to determine is some element is present. If element is present in all of your arrays - it will present in the first. So, go through first (unsorted) array and check if its element is in second and third.

If you take the shortest array as the first - it will make algorithm slightly faster too.

You did't store them on d[] the right way.

Once found you can skip the rest of a[] and b[] for that element of c[].

#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 found;
int d[5];
for(k=0; k<5; k++){
    found=0;
    for(j=0; j<5 && !found; j++){
        if (b[j]==c[k]) {
            for(i=0; i<5 && !found; i++){
                if(a[i]==b[j]) {
                    d[n++]=c[k];
                    found=1;
                }
            }
    }}}
//Iterate over the new array
for(i=0;i<5;i++)
    printf("%d\n",d[i]);
return 0;
}