Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.91/89: Рейтинг темы: голосов - 89, средняя оценка - 4.91
 Аватар для mat_for_c
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972

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

26.04.2013, 19:02. Показов 17213. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте.
У меня следующая задача:
Даны 2 множества A и B, причем множество B отсортировано по возрастанию. Необходимо получить индексы тех элементов множества А, которые содержатся в множестве В. Как это можно сделать максимально быстро на С++?

Пример:
A={4 3 5 1 7 0 2}; B={1 2 3}; => Ответ = {2 4 6};
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.04.2013, 19:02
Ответы с готовыми решениями:

Пересечение множеств
Вход — два множества натуральных чисел. Выход — их пересечение (перечисление элементов через пробел в любом порядке без повторений)...

Пересечение множеств
Есть такое задание: Создать класс- множество. Функции-члены реализуют добавление и удаление элемента, пересечение и размность множеств. ...

пересечение множеств
найти пересечение мнжества А и В. Результат вывести в другом множестве. заранее спс. извиняюсь если такое задание уже было

11
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
26.04.2013, 19:13
Первое, что приходит в голову -- бинарный поиск каждого элемента массива А в массиве Б.
0
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
26.04.2013, 19:28
А почему в примере получается 2 4 6 ?
0
 Аватар для mat_for_c
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
27.04.2013, 01:06  [ТС]
Цитата Сообщение от lazybiz Посмотреть сообщение
А почему в примере получается 2 4 6 ?
да, согласен. должно быть {2, 4, 7}

Добавлено через 3 минуты
Если я не ошибаюсь, бинарный поиск производится в отсортированном массиве. Это было бы хорошо, если бы искали индексы в В, но нам надо в А. Отсортировав множество А, мы потеряем исходные индексы
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
27.04.2013, 01:24
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
0
 Аватар для mat_for_c
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
27.04.2013, 02:32  [ТС]
Цитата Сообщение от Olivеr Посмотреть сообщение
Но учтите, что в векторе элементы могут повторятся. Это противоречит понятию множества.
К тому же, элементы в множестве не имеют индексов.
Согласен, получается что в мультимножестве А элементы могут повторяться, однако этого не происходит в множестве В по построению.
Понятно, что множество в ЯП задается через массив, поэтому мне и нужны "индексы элементов".

Но не будет ли Ваш метод долгим для довольно больших массивов? Ведь если у нас нет элемента в пересечении этих множеств, то пробегать весь массив... как-то не хочется. Задача стоит в решении наиболее быстрым способом. Вот я пытаюсь его найти...
0
 Аватар для IrineK
2023 / 1641 / 425
Регистрация: 23.02.2011
Сообщений: 6,002
Записей в блоге: 25
27.04.2013, 04:34
Есть ли ограничения на элементы множеств? В каких пределах они меняются?
0
алкокодер
 Аватар для UnsKneD
157 / 153 / 41
Регистрация: 27.12.2012
Сообщений: 550
27.04.2013, 05:07
mat_for_c, Пересечение множеств
0
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
27.04.2013, 10:24
Задачу можно решить бинарным поиском, а можно через 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 массив, в котором каждому элементу будет сопоставлен индекс первого вхождения.
0
 Аватар для Olivеr
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
27.04.2013, 11:17
может быть еще так
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
0
 Аватар для mat_for_c
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
27.04.2013, 15:34  [ТС]
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?
0
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
27.04.2013, 15:58
mat_for_c, даже, сильно медленнее на плохих тестах

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

Добавлено через 1 минуту
Не пишите на С++ быструю сортировку руками никогда используйте std::sort она работает за O(NlogN)
А обычные наивные реализации могут деградировать до O(N^2)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
27.04.2013, 15:58
Помогаю со студенческими работами здесь

Объединение, пересечение, разность множеств
#include &quot;stdafx.h&quot; #include &lt;fstream&gt; #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;clocale&gt; #include &lt;math.h&gt; ...

Найти пересечение и объединения заданных множеств
Здравствуйте. У меня следующая задача: Даны множества U={1,2,3,4,…,25} та три ее подмножества A={1,9,10,11,15,16,17,22},...

Пересечение, ообъединение, наименьший элемент пересечения множеств
&quot;Даны два множества A и B байтовых чисел. Найдите пересечение и объединение этих множеств и определите наименьший элемент пересечения...

Найти пересечение множеств ключей двух map
Добрый день! Имеется 2 map'а: map&lt;string, double&gt; map1; map&lt;string, double&gt; map2; Требуется сложить ключи, являющиеся общими...

Объединение, пересечение и разность множеств с помощью оператора SWITCH
Помогите пожалуйста написать программу объединение,пересечение и разность множеств с помощью оператора SWITCH ....ввод элементов с...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru