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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сравнение векторов http://www.cyberforum.ru/cpp-beginners/thread849456.html
Вот имеется вектор <bool> длиной допустим 5, а второй вектор <bool> длиной 200. Вот мне надо сравнить первый вектор с частью второго, зная размер первого. Вот так не получилось if(fs ==...
C++ Заполнить массив А(10) случайными числами. Подсчитать и вывести на экран количество элементов массива, кратных 7 и не кратных 3 1) Заполнить массив А(10) случайными числами. Подсчитать и вывести на экран количество элементов массива, кратных 7 и не кратных 3. 2)Дан массив R(5). Значения элементов массива ввести с... http://www.cyberforum.ru/cpp-beginners/thread849447.html
Дан одномерный массив,введенный с клавиатуры C++
Дан одномерный массив,введенный с клавиатуры. -Найти сумму неотрицательных элементов в каждой строчке. -Сформировать вектор В из элементов побочной диагонали
C++ Найти минимальный элемент в матрице и посчитать количество отрицательных элементов,расположенных выше главной диагонали.
Напишите программу формирования массива C(n,n) с помощью датчика случайных чисел из промежутка. -Найдите минимальный элемент и поменяйте его с первым элементом массива. -посчитать количество...
C++ хеширование http://www.cyberforum.ru/cpp-beginners/thread849436.html
Написать функцию int incl_lexm (char *p_lexm, char type _lexm), которая методом хеширования для строки, адресуемой p_lexm, определяет свободную позицию в таблице tabl, и если в ней отсутствует...
C++ Поиск минимального элемента идеально сбалансированного дерева Как найти минимальный элемент? Вообще не представляю. зы. Дерево поиска другой разговор. подробнее

Показать сообщение отдельно
Ternsip
660 / 188 / 6
Регистрация: 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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru