1

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

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

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

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

4
  • Сортировка + проход в поисках совпадения. O(N lg N) из-за сортировки. Если возможна та же сортировка подсчетом - O(N). Можно попробовать приспособить фильтр Блума, конечно, но тогда не будет точно известен элемент + возможны ложные срабатывания.
    – Harry
    28 фев 2018 в 13:41
  • Для ускорения можно подключить многопоточность. 28 фев 2018 в 14:04
  • 1
    Вместо сортировки можно свалить массив в std:set или в std::unordered_set, и пройтись поиском по второму... по факту эквивалентно предложению Harry, но с хешем сложность будет близка к O(N).
    – Fat-Zer
    28 фев 2018 в 14:34
  • Для того, чтобы говорить о множественной задаче, надо знать, какая часть остается неизменноой, а какая меняется. В любом случае, ни о каком константном времени не может быть и речи. 28 фев 2018 в 16:34

2 ответа 2

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
0

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

3
  • std::set_intersection требует отсортированных массивов на входе. 28 фев 2018 в 16:49
  • Верно. Но это вроде и в документации написано, вы это к чему ? Если про O(N), то я имел в виду сложность запроса, исключая предпосчёт( сортировку двух массивов). Причём N - размер пересечения, а не исходных массивов
    – vt-egorov
    28 фев 2018 в 21:21
  • К тому, что в данной задача массивы не упорядочены. Соответственно в любом решении, требующем сортированности, необходимо принимать во внимание затраты на сортировку. 28 фев 2018 в 21:23

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.