Пересечение множеств

Ноябрь 9th, 2011 § 1 comment

Есть два множества нужно найти их пересечение, каким образом это сделать за минимальное время. Можно для этих целей использовать STL . В этом случае нам нужно иметь два множества, обязательно отсортированных. Функция нахождения пересечения и сортировки находятся в заголовочном файле <algorithm>. Пример того как это сделать с помощью STL


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
 int first[] = {5,10,15,20,25};
 int second[] = {50,40,30,20,10};
 vector<int> v(10);
 vector<int>::iterator it;

 sort (first,first+5);     //  5 10 15 20 25
 sort (second,second+5);   // 10 20 30 40 50

 it=set_intersection (first, first+5, second, second+5, v.begin());
 cout << "intersection has " << int(it - v.begin()) << " elements.\n";
 return 0;
}

Этот код взят с cplusplus.com. Если же вы пишете на другом ЯП и считаете что нужно знать как все выполняется то смотрим дальше. Весь код приводить не буду, первое что нужно уяснить алгоритм работает на отсортированных множествах иначе, работать не будет, если не нравится сортировать то добро пожаловать в сложность O(N^2)., нам же этого не нужно. Быстро набросанный код для этого. Тут все еще есть стандартная функция сорт, можно было бы и самому реализовать, но хотел что бы листинг был как можно компактнее, тем более что основные алгоритмы для сортировки в блоге приведены тут и тут.

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
int result[10];
sort (first,first+5);
sort (second,second+5);
for(int i=0,k=0;i<sizeof(first);i++)
for(int j=0;j<sizeof(second);j++)
{
if(second[j]>first[i])
break;
if(first[i]==second[j])
{
result[k]=first[i];
k++;
break;
}
}
return 0;
}

Tagged

§ One Response to Пересечение множеств

  • Григорий пишет:

    А какой смысл сортировать первый массив, если сортировка его никак не учитывается. Имеет смысл если бы второй цикл начинать не сначала а с элемента который не совпал, тогда сложность будет O(n+m), в приведенном алгоритме, если все элементы первого множества меньше элементов второго, то сложность будет О(n*m) и приходим к “если не нравится сортировать то добро пожаловать в сложность O(N^2)., нам же этого не нужно”

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Смотреть фильмы онлайн