|
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
|
|
| 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 Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
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 .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|