Общий элемент двух массивов

118

02 марта 2018, 17:26

Имеется два массива (вектора, разницы нет какой контейнер использовать) нужно найти два элемента, которые есть и в первом и во втором. Кроме идей про перебор всех чисел ничего не придумал.

Можно конечно использовать lower_bound для оптимизации

Но я нуждаюсь в быстром ответе на запрос (константным в лучшем случаем, потому что массивов у меня может быть много и запросов тоже, около 1000).

Как это можно сделать ? возможно есть какой-то алгоритм решающий эту проблему.

Answer 1

vector<int> res;
vector<int>  fv{1, 4, 5, 9, 23, 12, 24, 45, 56, 75};
vector<int>  sv {3, 6, 7, 23, 11, 12, 34, 46, 8, 19};
set_intersection(fv.begin(), fv.end(), sv.begin(), sv.end(), back_inserter(res));
    // элементы вектора res

Answer 2

К сожалению не могу добавлять комментариев. А std::set_intersection не поможет ? Если массива только только два, то вычислив пересечение и положив его в хэш таблицу (std::unordered_set), для каждого запроса будет почти O(N)