Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 586
Завершенные тесты: 2
26.04.2013, 19:02     Пересечение множеств #1
Здравствуйте.
У меня следующая задача:
Даны 2 множества A и B, причем множество B отсортировано по возрастанию. Необходимо получить индексы тех элементов множества А, которые содержатся в множестве В. Как это можно сделать максимально быстро на С++?

Пример:
A={4 3 5 1 7 0 2}; B={1 2 3}; => Ответ = {2 4 6};
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
26.04.2013, 19:13     Пересечение множеств #2
Первое, что приходит в голову -- бинарный поиск каждого элемента массива А в массиве Б.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
26.04.2013, 19:28     Пересечение множеств #3
А почему в примере получается 2 4 6 ?
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 586
Завершенные тесты: 2
27.04.2013, 01:06  [ТС]     Пересечение множеств #4
Цитата Сообщение от lazybiz Посмотреть сообщение
А почему в примере получается 2 4 6 ?
да, согласен. должно быть {2, 4, 7}

Добавлено через 3 минуты
Если я не ошибаюсь, бинарный поиск производится в отсортированном массиве. Это было бы хорошо, если бы искали индексы в В, но нам надо в А. Отсортировав множество А, мы потеряем исходные индексы
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.04.2013, 01:24     Пересечение множеств #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    vector<int> A = {4, 3, 5, 1, 7, 0, 2};
    vector<int> B = {1, 2, 3};
 
    for (auto it = begin(A); it != end(A); it++) {
        auto pos = find(B.begin(), B.end(), *it);
        if (pos != B.end())
            cout << distance(A.begin(), it) + 1;
    }
    return 0;
}
Добавлено через 2 минуты
Но учтите, что в векторе элементы могут повторятся. Это противоречит понятию множества.
К тому же, элементы в множестве не имеют индексов.
Еще гляньте std::set
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 586
Завершенные тесты: 2
27.04.2013, 02:32  [ТС]     Пересечение множеств #6
Цитата Сообщение от Olivеr Посмотреть сообщение
Но учтите, что в векторе элементы могут повторятся. Это противоречит понятию множества.
К тому же, элементы в множестве не имеют индексов.
Согласен, получается что в мультимножестве А элементы могут повторяться, однако этого не происходит в множестве В по построению.
Понятно, что множество в ЯП задается через массив, поэтому мне и нужны "индексы элементов".

Но не будет ли Ваш метод долгим для довольно больших массивов? Ведь если у нас нет элемента в пересечении этих множеств, то пробегать весь массив... как-то не хочется. Задача стоит в решении наиболее быстрым способом. Вот я пытаюсь его найти...
IrineK
Заблокирован
27.04.2013, 04:34     Пересечение множеств #7
Есть ли ограничения на элементы множеств? В каких пределах они меняются?
UnsKneD
алкокодер
 Аватар для UnsKneD
153 / 149 / 11
Регистрация: 27.12.2012
Сообщений: 548
27.04.2013, 05:07     Пересечение множеств #8
mat_for_c, Пересечение множеств
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
27.04.2013, 10:24     Пересечение множеств #9
Задачу можно решить бинарным поиском, а можно через set, сути не меняет.
В set асимптотика O(logN) для поиска элемента и для добавления. => Вся асимптотика O(N*logN + M*logN) M - количество эл-ов во втором мн-ве, N - в первом. Для реадизации с бинарным поиском асимптотика Асболютно такая же, т.к. массив сначала надо отсортировать, а потом бинпоиск по нему => O(N*logN + M*logN).
Советую делать через set (множество), если вам специально не задали эту задачу через бинпоиск.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <set>
#include <vector>
 
using namespace std; 
 
int main(){
    int n, m, temp;
    cin >> n >> m;
    set <int> a, ans; 
    for (int i = 0; i < n; i++){
        cin >> temp;
        a.insert(temp);
    }
    for (int i = 0; i < m; i++){
        cin >> temp;
        if (a.count(temp) != 0) ans.insert(temp);
    }   
    cout << ans.size() << endl;
    for (set <int>::iterator it = ans.begin(); it != ans.end(); ++it){
        cout << *it << " ";
    }
    return 0;
}
Добавлено через 2 минуты
Но в этой задаче я ищу не индексы, а общие элементы. Чтобы искать индексы создайте ещё 1 массив, в котором каждому элементу будет сопоставлен индекс первого вхождения.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.04.2013, 11:17     Пересечение множеств #10
может быть еще так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main()
{
    int A[7] = { 4, 3, 5, 1, 7, 0, 2 };
    set<int> B = {1, 2, 3};
    for (auto it = begin(A); it != end(A); it++) {
        auto pos = find(B.begin(), B.end(), *it );
        if (pos != B.end())
            cout << distance(begin(A), it) + 1;
    }
 
    return 0;
}
Вам ведь нужно учитывать и порядок и индексы?
Я думал хранить данные в set<pair<int, int>>(значение, индекс) и set<int>(значение), но вывод получается 472
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 586
Завершенные тесты: 2
27.04.2013, 15:34  [ТС]     Пересечение множеств #11
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
bool* id_rows;
void intersect(double* a, double* b, long long n, long long k, long long* id_sort)
{
// функция для нахождения пересечения множеств
// точнее для индексов пересечения
    long long i = 0;
    long long j = 0;
    while (i != n && j != k)
    {
        if(a[i] < b[j])
            ++i;
        else
            if(b[j] < a[i])
                ++j;
            else {
                // запись индекса
                id_rows[id_sort[i]] = true;
                ++i;
            }
    }
}
 
void main()
{
    ...
    id_rows = new bool[len_indexnW];
    memset(id_rows, 0, len_indexnW);
    // создаем массив индексов
    long long* id = new long long[len_indexnW];
    for (long long i = 0; i < len_indexnW; ++i)
    {
        id[i] = i;
    }
    for (long long i = 0; i < col_count-1; ++i)
    {
        ...
        // массив индексов, который будем сортировать 
        // вместе с исходным множеством А
        long long* id_sort = new long long[len_indexnW];
        memcpy(id_sort, id, len_indexnW * sizeof(long long));
        // быстрая сортировка
        quicksort(Mnw_column[i], id_sort, 0, len_indexnW-1);
        intersect(Mnw_column[i], nWfeatValues, len_indexnW, len_diff, id_sort);
    }
    long long* RowZerosMw = NULL;
    long long len_RowZerosMw = 0;
    for (long long i = 0; i < len_indexnW; ++i)
    {
        if(id_rows[i] == true)
        {           
            RowZerosMw = (long long*)realloc(RowZerosMw,  (++len_RowZerosMw)*sizeof(long long));
            RowZerosMw[len_RowZerosMw-1] = i;
        }
    }
}
Что можете сказать про такой метод? Будет ли он работать быстрее, чем через set?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2013, 15:58     Пересечение множеств
Еще ссылки по теме:

Найти пересечение множеств ключей двух map C++
Объединение, пересечение и разность множеств с помощью оператора SWITCH C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
27.04.2013, 15:58     Пересечение множеств #12
mat_for_c, даже, сильно медленнее на плохих тестах

Добавлено через 5 минут
Мало того, что он очень громоздкий, так ещё и работает за квадрат в худшем случае

Добавлено через 1 минуту
Не пишите на С++ быструю сортировку руками никогда используйте std::sort она работает за O(NlogN)
А обычные наивные реализации могут деградировать до O(N^2)
Yandex
Объявления
27.04.2013, 15:58     Пересечение множеств
Ответ Создать тему
Опции темы

Текущее время: 04:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru