Другие языки программирования и технологии

алгоритм... по нахождению общих элементов двух массивов

помогите найти алгоритм по нахождению общих элементов двух массивов... Встречаются только кустарные варианты... на algolist.manual нашел реализацию на ином языке, не понятном мне... без комментариев вообще... то есть что за что отвечает переменная я хз... тупо алгоритм... синтаксис который могу примерно предположить так как похож на lua. помогите найти или перевести этот алгоритм на си или с++. с комментариями.... Подарок за лучший ответ гарантирую)))
А вот и сам алгоритм: язык не знаю какой

касательно палок я тоже хз, может быть они и не нужны там... ну крайне стремный синтаксис...
https://pastebin.com/uVsf0CUQ
Это же Паскаль. "Палки" не нужны, в фигурных скобках - комментарии, что останется - там уже всё понятно должно быть.
Вадим Кириков
Вадим Кириков
24 295
Лучший ответ
Александер Витвицкий а можете описать что такое переменная k1, l1, k, x[], y[]....а то я просто даже сути не могу уловить....
Да, и еще ты должен был написать:
Даны два возрастающих массива целых чисел x[1k] и y[1l] Найти количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j) (Число действий порядка k+l).
Тогда становится и алгоритм понятен.
Александер Витвицкий Куйня какая то получилась.... это разве алгоритм... нихера он не находит... тупо инкрементирует счетчики.. вот пиздюки.. блин залили херню....
#include <iostream>
#include <windows.h>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

template<class T>
void Print_(const T &);

int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
srand(time(0));
system("color 0A");

cout << "Введите длину массива 1 и 2 через пробел ";
size_t n1, n2;
cin >> n1 >> n2;
cout << "Введите левый и правый терминал генерируемых случайных чисел ";
int mi, ma;
cin >> mi >> ma;

auto Init = [&mi, &ma]()
{
return mi + rand() % (ma - mi + 1);
};

vector<int> v1(n1);
vector<int> v2(n2);
vector<int> v3;
generate(v1.begin(), v1.end(), Init);
generate(v2.begin(), v2.end(), Init);

cout << endl;
cout << "Содержание первого массива" << endl;
Print_(v1);
cout << "Содержание второго массива" << endl;
Print_(v2);
cout << endl;

set<int> s1(v1.begin(), v1.end());
set<int> s2(v2.begin(), v2.end());

set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(v3));

cout << "Элементы, которые есть и в первом и во втором массиве" << endl;
Print_(v3);
cout << endl;

system("pause");
return 0;
}

template<class T>
void Print_(const T &v)
{
for (const auto &t : v)
{
cout << t << " ";
}
cout << endl;
}
Александер Витвицкий ну это чисто код... весь сыр сокрыт в set_intersection....я затестю конечно этот вариант и другие. но думаю контейнера не лучший способ выиграть по скорости.
Александер Витвицкий не бро... алгоритм остойный.... один из наихудших вариантов
Александер Витвицкий сравнивалось с
vector Intersect(int * A, int * B, int n, int m)
{
sort(A, A + n);
sort(B, B + m);
vector result; // сюда будем записывать элементы

int x = 0, y = 0;
while (x < n && y < m) { // ищем совпадающие элементы
if (A[x] < B[y]) x++;
else if (A[x] > B[y]) y++;
else { result.push_back(A[x]); x++; y++; }
}
return result;
}

// Попробую его еще ускорить бинарным поиском
1) сортируем оба массива
2) std::set_intersection алгоритм описан по ссылке

https://ideone.com/wYde0K

что стоит отдельно отметить
1) нужна сортировка. т. е. обе входных коллекции подвергаются изменению
2) результат тоже будет отсортирован
3) если элемент встречается несколько раз и в той и в другой коллекции, то и в выводе он будет несколько раз.

если нужно без повторов, вместо сортировки на месте. можно скопировать данные в 2 множества.
это упорядочит элементы и исключит повторы

https://ideone.com/HZqK7u

вот еще вариант. без повторов, в порядке сортировки второго массива, и в теории самый производительный - в среднем линейное время от длины обоих массивов
https://ideone.com/ekYV0f
РЮ
Руслан Юдин
7 029
Александер Витвицкий контейнеры опять же.... они не могут быть быстрейшими так как они тормозятся исключениями (((( но все равно спасибо. я сравню их по времени с другими на разных данных...

Похожие вопросы