Хранение чисел в массиве в 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).

Answer 2

Предварительно отсортируйте второй и третий массивы и используйте двоичный поиск по ним, чтобы определить, присутствует ли какой-либо элемент.Если элемент присутствует во всех ваших массивах - он будет представлен в первом.Итак, пройдите первый (несортированный) массив и проверьте, находится ли его элемент во втором и третьем.

Если вы возьмете самый короткий массив в качестве первого - это также сделает алгоритм немного быстрее.

Answer 3

Ваша ошибка в том, что вы используете один из трех вложенных счетчиков (которые используются для индексации входных массивов) в качестве индекса в выходном массиве.Вам необходимо иметь четвертый индекс (назовем его n), который начинается с нуля и увеличивается каждый раз, когда найдено удовлетворительное значение.

Answer 4

Вы не правильно сохранили их на d [].

Найдя, вы можете пропустить остальные a [] и b [] для этого элемента 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;
}