Рубрики

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

Дано n наборов целых чисел разных размеров. Каждый набор может также содержать дубликаты. Как найти пересечение всех множеств. Если элемент присутствует несколько раз во всех наборах, он должен быть добавлен столько раз в результате.

Например, рассмотрим три набора {1,2,2,3,4} {2,2,3,5,6} {1,3,2,2,6}. Пересечение данных множеств должно быть {2,2,3}

Ниже приведен эффективный подход к решению этой проблемы.

1. Сортировать все наборы.
2. Возьмите наименьший набор и вставьте все элементы и их частоты в карту.
3. Для каждого элемента на карте сделайте следующее
… .. а. Если элемент отсутствует в любом наборе, игнорируйте его
… .. б. Найти частоту элемента в каждом наборе (используя бинарный поиск). Если это меньше, чем частота на карте, обновите частоту
… .. в. Если элемент найден во всех наборах, добавьте его в результат.

Вот реализация C ++ вышеупомянутого подхода.

// C ++ программа для поиска пересечения n множеств
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

  
// Основная функция, которая получает набор множеств в качестве параметра и
// возвращает множество, содержащее пересечение всех множеств

vector <int> getIntersection(vector < vector <int> > &sets)

{

    vector <int> result;  // Для сохранения набора данных

    int smallSetInd = 0;  // Инициализируем индекс наименьшего множества

    int minSize = sets[0].size(); // Инициализируем размер наименьшего набора

  

    // сортируем все наборы, а также находим наименьший набор

    for (int i = 1 ; i < sets.size() ; i++)

    {

        // сортируем этот набор

        sort(sets[i].begin(), sets[i].end());

  

        // обновить minSize, если необходимо

        if (minSize > sets[i].size())

        {

            minSize = sets[i].size();

            smallSetInd = i;

        }

    }

  

    map<int,int> elementsMap;

  

    // Добавить все элементы наименьшего набора на карту, если они уже есть,

    // обновляем частоту

    for (int i = 0; i < sets[smallSetInd].size(); i++)

    {

        if (elementsMap.find( sets[smallSetInd][i] ) == elementsMap.end())

            elementsMap[ sets[smallSetInd][i] ] = 1;

        else

            elementsMap[ sets[smallSetInd][i] ]++;

    }

  

    // перебираем элементы карты, чтобы увидеть, присутствуют ли они в

    // оставшиеся множества

    map<int,int>::iterator it;

    for (it = elementsMap.begin(); it != elementsMap.end(); ++it)

    {

        int elem = it->first;

        int freq = it->second;

  

        bool bFound = true;

  

        // перебирать все множества

        for (int j = 0 ; j < sets.size() ; j++)

        {

            // Если этот набор не является наименьшим, тогда выполняем в нем бинарный поиск

            if (j != smallSetInd)

            {

                // Если элемент найден в этом наборе, то найти его частоту

                if (binary_search( sets[j].begin(), sets[j].end(), elem ))

                {

                   int lInd = lower_bound(sets[j].begin(), sets[j].end(), elem)

                                                            - sets[j].begin();

                   int rInd = upper_bound(sets[j].begin(), sets[j].end(), elem)

                                                            - sets[j].begin();

  

                   // Обновляем минимальную частоту, если необходимо

                   if ((rInd - lInd) < freq)

                       freq = rInd - lInd;

                }

                // Если элемент отсутствует в любом наборе, то нет необходимости

                // перейти к этому элементу.

                else

                {

                    bFound = false;

                    break;

                }

            }

        }

  

        // Если элемент был найден во всех наборах, то добавить его в результат 'freq' раз

        if (bFound)

        {

            for (int k = 0; k < freq; k++)

                result.push_back(elem);

        }

    }

    return result;

}

  
// Вспомогательная функция для печати набора элементов

void printset(vector <int> set)

{

    for (int i = 0 ; i < set.size() ; i++)

        cout<<set[i]<<" ";

}

  

  
// Прецедент

void TestCase1()

{

    vector < vector <int> > sets;

    vector <int> set1;

    set1.push_back(1);

    set1.push_back(1);

    set1.push_back(2);

    set1.push_back(2);

    set1.push_back(5);

  

    sets.push_back(set1);

  

    vector <int> set2;

    set2.push_back(1);

    set2.push_back(1);

    set2.push_back(4);

    set2.push_back(3);

    set2.push_back(5);

    set2.push_back(9);

  

    sets.push_back(set2);

  

    vector <int> set3;

    set3.push_back(1);

    set3.push_back(1);

    set3.push_back(2);

    set3.push_back(3);

    set3.push_back(5);

    set3.push_back(6);

  

    sets.push_back(set3);

  

    vector <int> r = getIntersection(sets);

  

    printset(r);

  
}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    TestCase1();

    return 0;

}

Выход:

1 1 5

Сложность времени: пусть будет «n» списков, а средний размер списков будет «m». Фаза сортировки занимает O (n * m * log m) времени (сортировка n списков со средней длиной m). Фаза поиска занимает O (m * n * log m) времени. (для каждого элемента в списке мы ищем n списков с log m time). Таким образом, общая сложность времени составляет O (n * m * log m).

Вспомогательное пространство: O (м) пространство для хранения карты.

Эта статья составлена Рави Чандрой Энаганти . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes