Как найти общие элементы у трех массивов?

Question

[g hh]

Надо переделать функцию passForCommonElements(), чтобы она находила и выводила по одному разу общие элементы трех массивов.

#include<iostream>

using namespace std;

template < typename T>
void passForCommonElements(T array1[], T array2[], T array3[], int size1, int size2, int size3) //поиск и вывод общих элементов массивы 
{
	T* arrayCommonElements = new T[size1]();

	int g = 0;
	int i = 0;
	int j = 0;
	int k = 0;
	int p = 0;

	while (g)
	while (g < size1)
	{

		while (i < size1)
		{
			j = 0;
			while (j < size2)
			{
				if (array1[i] == array2[j])
				{
					k = 0;
					while (k < size3)
					{
						if (array1[i] == array3[k])
						{
							p = 0;
							while (p < size1)
							{
								if (array1[i] != arrayCommonElements[p])
								{
									arrayCommonElements[g] = array1[i];
								}
								p++;
							}
						}
						k++;
					}
				}
				j++;
			}
			i++;
		}
		
	}
	
	int h = 0;
	cout << "Общие элементы трех массивов: ";
	while (h < size1)
	{
		cout << array1[h] << " ";
		h++;
	}
	cout << endl;
	

	
	delete[] arrayCommonElements;
}

template < typename T1>
void outputElements(T1 array1[], T1 array2[], T1 array3[], int size1, int size2, int size3) //поиск и вывод общих элементов массивы 
{
	int i = 0;
	cout << "Элементы первого массива: ";
	while (i < size1)
	{
		cout << array1[i] << " ";
		i++;
	}
	cout << endl;

	i = 0;
	cout << "Элементы второго массива: ";
	while (i < size2)
	{
		cout << array2[i] << " ";
		i++;
	}
	cout << endl;

	i = 0;
	cout << "Элементы третьего массива: ";
	while (i < size3)
	{
		cout << array3[i] << " ";
		i++;
	}
	cout << endl;
}

void inputElementsFloat(float* array1, float* array2, float* array3, int size1, int size2, int size3)
{
	int i = 0;
	while (i < size1)
	{
		cout << "Введите значение элемента первого массива под индексом " << i << ": " << endl;
		cin >> array1[i];
		i++;
	}
	cout << endl;

	i = 0;
	while (i < size2)
	{
		cout << "Введите значение элемента второго массива под индексом " << i << ": " << endl;
		cin >> array2[i];
		i++;
	}
	cout << endl;

	i = 0;
	while (i < size3)
	{
		cout << "Введите значение элемента третьего массива под индексом " << i << ": " << endl;
		cin >> array3[i];
		i++;
	}
	cout << endl;
}

void inputElementsInt(int* array1, int* array2, int* array3, int size1, int size2, int size3)
{
	int i = 0;
	while (i < size1)
	{
		cout << "Введите значение элемента первого массива под индексом " << i << ": " << endl;
		cin >> array1[i];
		i++;
	}
	cout << endl;

	i = 0;
	while (i < size2)
	{
		cout << "Введите значение элемента второго массива под индексом " << i << ": " << endl;
		cin >> array2[i];
		i++;
	}
	cout << endl;

	i = 0;
	while (i < size3)
	{
		cout << "Введите значение элемента третьего массива под индексом " << i << ": " << endl;
		cin >> array3[i];
		i++;
	}
	cout << endl;
}


int main()
{
	setlocale(LC_ALL, "ru");

	int k, m, n;
	int arrayType;

	cout << "Введите размер первого массива:" << endl;
	cin >> k;
	cout << endl << "Введите размер второго массива:" << endl;
	cin >> m;
	cout << endl << "Введите размер третьего массива:" << endl;
	cin >> n;

	cout << endl << "Введите значение типа массива:" << endl;
	cout << endl << "0 - float";
	cout << endl << "1 - int" << endl << endl;
	cin >> arrayType;
	if (arrayType)
	{
		
		int* array1 = new int[k];
		int* array2 = new int[m];
		int* array3 = new int[n];


		inputElementsInt(array1, array2, array3, k, m, n);
		
		outputElements(array1, array2, array3, k, m, n);

		passForCommonElements(array1, array2, array3, k, m, n);

		delete[] array1;
		delete[] array2;
		delete[] array3;
	}
	else
	{
		
		float* array1 = new float[k];
		float* array2 = new float[m];
		float* array3 = new float[n];

		inputElementsFloat(array1, array2, array3, k, m, n);

		outputElements(array1, array2, array3, k, m, n);

		passForCommonElements(array1, array2, array3, k, m, n);

		delete[] array1;
		delete[] array2;
		delete[] array3;
	}

	
	
	return 0;
}

Answer 1

[WAR_VIK]

Вот код покороче:

#include <iostream>

template <typename T>
void commonElem(T a[], T a2[], T a3[], int len, int len2, int len3) {
  std::cout<<"Common elements arrays is: ";
  for(int i{0}; i < len; ++i) {
    bool f2{false}, f3{false};
    for(int j{0}; j < len2; ++j) if(a[i] == a2[j]) f2 = true;
    for(int k{0}; k < len3; ++k) if(a[i] == a3[k]) f3 = true;
    if(f2 && f3) std::cout << a[i] << ' ';
  }
}

int main() {
int arr[]{23,12,54,2,7}, arr2[]{2,23,1,65}, arr3[]{43,2,76,4,23,8,96};
int l = std::size(arr), l2 = std::size(arr2), l3 = std::size(arr3);
commonElem(arr, arr2, arr3, l, l2, l3);
return 0;
}

Answer 2

[Wataru]

Какой ужасный алгоритм! Лучше запихнуть первые два массива в hash-set (std::unordered_set). А потом при проходе по третьему массиву просто проверить, что этот элемент есть в первых двух set-ах.

Если элементы могут повторятся, но выводить надо только один раз, то заведите еще один unordered_set, куда добавляйте элементы, которые вы добавили в ответ. Естественно, перед добавлением элемента в ответ, проверьте, а не содержится ли он уже в этом set-е.

И код получится раз в 10 меньше и работать будет на пару порядков быстрее.

Comments

[res2001]

Я бы загнал первый массив в std::unordered_map, где ключ - это значение очередного элемента первого массива, а значение - счетчик. Для всех элементов первого массива, счетчик выставляем в 1.
Дальше ищем каждое значение второго и третьего массива в mapе, если найдено - инкрементируем счетчик.
Выводим все элементы из mapы, у которых счетчик равен 3.

Стоит выбрать самый наименьший по размеру массив и его брать как первый.

[Wataru]

res2001, Только над аккуратно обрабатывать повторяющиеся элементы. Ведь если элемент 3 раза входит в первый и больше ни в один, то вы его выведите. Можно, например, биты в 1 устанавливать для разных массивов. Тогда это решение будет почти полностью эквивалентно моему. Если в первом массиве меньше элементов, чем во втором - то ваше решение будет занимать меньше памяти. Если наоборот - то мое.

Answer 3

[Adamos]

Второй вопрос ТС за день, и второй раз достаточно внимательно прочитать собственный код, чтобы найти ошибку.
Предлагаю просто игнорировать этого лентяя, джентльмены.