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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
mat_for_c
141 / 136 / 29
Регистрация: 26.04.2013
Сообщений: 663
Завершенные тесты: 2
#1

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

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

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

Пример:
A={4 3 5 1 7 0 2}; B={1 2 3}; => Ответ = {2 4 6};
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.04.2013, 19:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пересечение множеств (C++):

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

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

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

Объединение, пересечение, разность множеств - C++
#include "stdafx.h" #include <fstream> #include <iostream> #include <conio.h> #include <clocale> #include <math.h> ...

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
26.04.2013, 19:13 #2
Первое, что приходит в голову -- бинарный поиск каждого элемента массива А в массиве Б.
castaway
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
26.04.2013, 19:28 #3
А почему в примере получается 2 4 6 ?
mat_for_c
141 / 136 / 29
Регистрация: 26.04.2013
Сообщений: 663
Завершенные тесты: 2
27.04.2013, 01:06  [ТС] #4
Цитата Сообщение от lazybiz Посмотреть сообщение
А почему в примере получается 2 4 6 ?
да, согласен. должно быть {2, 4, 7}

Добавлено через 3 минуты
Если я не ошибаюсь, бинарный поиск производится в отсортированном массиве. Это было бы хорошо, если бы искали индексы в В, но нам надо в А. Отсортировав множество А, мы потеряем исходные индексы
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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
141 / 136 / 29
Регистрация: 26.04.2013
Сообщений: 663
Завершенные тесты: 2
27.04.2013, 02:32  [ТС] #6
Цитата Сообщение от Olivеr Посмотреть сообщение
Но учтите, что в векторе элементы могут повторятся. Это противоречит понятию множества.
К тому же, элементы в множестве не имеют индексов.
Согласен, получается что в мультимножестве А элементы могут повторяться, однако этого не происходит в множестве В по построению.
Понятно, что множество в ЯП задается через массив, поэтому мне и нужны "индексы элементов".

Но не будет ли Ваш метод долгим для довольно больших массивов? Ведь если у нас нет элемента в пересечении этих множеств, то пробегать весь массив... как-то не хочется. Задача стоит в решении наиболее быстрым способом. Вот я пытаюсь его найти...
IrineK
Заблокирован
27.04.2013, 04:34 #7
Есть ли ограничения на элементы множеств? В каких пределах они меняются?
UnsKneD
алкокодер
154 / 150 / 11
Регистрация: 27.12.2012
Сообщений: 548
27.04.2013, 05:07 #8
mat_for_c, Пересечение множеств
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
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 831
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
141 / 136 / 29
Регистрация: 26.04.2013
Сообщений: 663
Завершенные тесты: 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?
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)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2013, 15:58
Привет! Вот еще темы с ответами:

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

Осуществить все операции над элементами множеств: пересечение, объединение, ... - C++
Привет всем. Помогите найти ошибку в коде. Задание такое: Программа позволит осуществить все операции над элементами множеств:...

Определить, есть ли в данном тексте пара слов, пересечение множеств символов которых пусто. - C++
подскажите!!!!! Определить, есть ли в данном тексте пара слов, пересечение множеств символов которых пусто.

Заданы два множества точек на плоскости. Построить пересечение и разность этих множеств. Дописать программу - C++
Помогите написать, дописать эту программу очень нужна ваша помощь... Задание:заданы два множества точек на плоскости. Построить...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
27.04.2013, 15:58
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru