|
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
|
|
Пересечение множеств26.04.2013, 19:02. Показов 17241. Ответов 11
Метки нет (Все метки)
Здравствуйте.
У меня следующая задача: Даны 2 множества A и B, причем множество B отсортировано по возрастанию. Необходимо получить индексы тех элементов множества А, которые содержатся в множестве В. Как это можно сделать максимально быстро на С++? Пример: A={4 3 5 1 7 0 2}; B={1 2 3}; => Ответ = {2 4 6};
0
|
|
| 26.04.2013, 19:02 | |
|
Ответы с готовыми решениями:
11
Пересечение множеств Пересечение множеств пересечение множеств |
|
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
|
|
| 26.04.2013, 19:13 | |
|
Первое, что приходит в голову -- бинарный поиск каждого элемента массива А в массиве Б.
0
|
|
|
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
|
||
| 27.04.2013, 01:06 [ТС] | ||
|
Добавлено через 3 минуты Если я не ошибаюсь, бинарный поиск производится в отсортированном массиве. Это было бы хорошо, если бы искали индексы в В, но нам надо в А. Отсортировав множество А, мы потеряем исходные индексы
0
|
||
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
| 27.04.2013, 01:24 | ||||||
Но учтите, что в векторе элементы могут повторятся. Это противоречит понятию множества. К тому же, элементы в множестве не имеют индексов. Еще гляньте std::set
0
|
||||||
|
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
|
||
| 27.04.2013, 02:32 [ТС] | ||
|
Понятно, что множество в ЯП задается через массив, поэтому мне и нужны "индексы элементов". Но не будет ли Ваш метод долгим для довольно больших массивов? Ведь если у нас нет элемента в пересечении этих множеств, то пробегать весь массив... как-то не хочется. Задача стоит в решении наиболее быстрым способом. Вот я пытаюсь его найти...
0
|
||
|
алкокодер
157 / 153 / 41
Регистрация: 27.12.2012
Сообщений: 550
|
|
| 27.04.2013, 05:07 | |
|
mat_for_c, Пересечение множеств
0
|
|
|
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 (множество), если вам специально не задали эту задачу через бинпоиск.
Но в этой задаче я ищу не индексы, а общие элементы. Чтобы искать индексы создайте ещё 1 массив, в котором каждому элементу будет сопоставлен индекс первого вхождения.
0
|
||||||
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
| 27.04.2013, 11:17 | ||||||
|
может быть еще так
Я думал хранить данные в set<pair<int, int>>(значение, индекс) и set<int>(значение), но вывод получается 472
0
|
||||||
|
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
|
||||||
| 27.04.2013, 15:34 [ТС] | ||||||
0
|
||||||
|
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
|
|
| 27.04.2013, 15:58 | |
|
Помогаю со студенческими работами здесь
12
Объединение, пересечение, разность множеств Найти пересечение и объединения заданных множеств Пересечение, ообъединение, наименьший элемент пересечения множеств
Объединение, пересечение и разность множеств с помощью оператора SWITCH Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ВВЕДЕНИЕ
Введу сокращения:
аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
|
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi
ветка по-частям.
коммит Create переделка под биомассу. txt
вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
|
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ *
Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях.
Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её.
Последовательность действий:. . .
|
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
|
|
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение.
И на уровне агентов добавится между грибами или бактериями взаимодействий.
До того я пробовал подход через многомерные массивы,. . .
|
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Налог на собак: https:/ / **********/ gallery/ V06K53e
Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf
Пост отсюда. . .
|
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop?
Ниже её машинный перевод.
После долгих разбирательств я наконец-то вернула себе. . .
|
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод
Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод.
Thinkpad X220 Tablet —. . .
|