помогите найти алгоритм по нахождению общих элементов двух массивов... Встречаются только кустарные варианты... на algolist.manual нашел реализацию на ином языке, не понятном мне... без комментариев вообще... то есть что за что отвечает переменная я хз... тупо алгоритм... синтаксис который могу примерно предположить так как похож на lua. помогите найти или перевести этот алгоритм на си или с++. с комментариями.... Подарок за лучший ответ гарантирую)))
А вот и сам алгоритм: язык не знаю какой
касательно палок я тоже хз, может быть они и не нужны там... ну крайне стремный синтаксис...
https://pastebin.com/uVsf0CUQ
Другие языки программирования и технологии
алгоритм... по нахождению общих элементов двух массивов
Это же Паскаль. "Палки" не нужны, в фигурных скобках - комментарии, что останется - там уже всё понятно должно быть.
Александер Витвицкий
а можете описать что такое переменная k1, l1, k, x[], y[]....а то я просто даже сути не могу уловить....
Да, и еще ты должен был написать:
Даны два возрастающих массива целых чисел x[1k] и y[1l] Найти количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j) (Число действий порядка k+l).
Тогда становится и алгоритм понятен.
Даны два возрастающих массива целых чисел 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;
}

#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;
}
// Попробую его еще ускорить бинарным поиском
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
2) std::set_intersection алгоритм описан по ссылке
https://ideone.com/wYde0K
что стоит отдельно отметить
1) нужна сортировка. т. е. обе входных коллекции подвергаются изменению
2) результат тоже будет отсортирован
3) если элемент встречается несколько раз и в той и в другой коллекции, то и в выводе он будет несколько раз.
если нужно без повторов, вместо сортировки на месте. можно скопировать данные в 2 множества.
это упорядочит элементы и исключит повторы
https://ideone.com/HZqK7u
вот еще вариант. без повторов, в порядке сортировки второго массива, и в теории самый производительный - в среднем линейное время от длины обоих массивов
https://ideone.com/ekYV0f
Александер Витвицкий
контейнеры опять же.... они не могут быть быстрейшими так как они тормозятся исключениями (((( но все равно спасибо. я сравню их по времени с другими на разных данных...
Похожие вопросы
- нахождение наибольшего элемента массива через функцию
- Помогите с С++. Надо найти произведение элементов одномерного массива между первым и последним 0.
- Помогите найти алгоритм подбора множителей к числам заданного массива, сумма произведений которых равна заданному числу
- дан двумерный массив С(3,4).Получите новый массив А путём увеличения всех элементов исходного массива на число С.
- Как найти кол-во одинаковых элементов в массиве? Подскажите алгоритм.
- Удаление повторяющихся элементов из массива С++
- №1.Как вычислить произведение элементов массива(1..5)В Паскале=)))№2.Найти наименьший элемент в массиве!Тоже в Паскале)
- задачка PAscal. найти сумму положительных элементов массива, расположенных до минимального элемента этого массива
- Как удалить нулевые элементы из массива C++. Помогите написать код для того чтобы из массива удалить все нулевые элементы
- C#. Элементы одномерного массива размером 7, которые больше среднего значения элементов массива, заменить на 0.