Блог

Главная - Вопросы по программированию - Пересечение векторов в C

Пересечение векторов в C

#c

#c #вектор #пересечение

Вопрос:

У меня есть эта функция

 vector<string> instersection(const vector<string> amp;v1, const vector<string> amp;v2);

У меня есть два вектора строк, и я хочу найти строки, которые присутствуют в обоих, которые затем заполняют третий вектор общими элементами.

Если мои векторы…

 v1 = <"a","b","c">
v2 = <"b","c">

Комментарии:

1. сортируйте () векторы, а затем используйте один цикл for, который просматривает оба вектора одновременно, всегда продвигая меньший. Затем просто соберите общие элементы.

2. for перебирайте один вектор и внутри этого делайте for через другой.

Ответ №1:

Попробуйте std::set_intersection , например:

 #include <algorithm> //std::sort
#include <iostream> //std::cout
#include <string> //std::string
#include <vector> //std::vector

std::vector<std::string> intersection(std::vector<std::string> v1,
                                      std::vector<std::string> v2){
    std::vector<std::string> v3;

    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::set_intersection(v1.begin(),v1.end(),
                          v2.begin(),v2.end(),
                          back_inserter(v3));
    return v3;
}

int main(){
    std::vector<std::string> v1 {"a","b","c"};
    std::vector<std::string> v2 {"b","c"};

    auto v3 = intersection(v1, v2);

    for(std::string n : v3)
        std::cout << n << ' ';
}

Комментарии:

1. Это O(n log n), где n — максимальное значение двух размеров. Почему бы просто не создать хэш-набор, состоящий из записей одного из векторов, а затем линейно пройти через другой вектор, проверяя их? Это O (n m) времени, O (m) памяти. Я вижу, что решение, которое я предлагаю, менее удобно для кэша, в дополнение к использованию большего объема памяти.

2. Я думаю, что OP не сказал, что векторы отсортированы.

Ответ №2:

Вам нужно отсортировать только меньший вектор. Затем выполните один проход по большему вектору и проверьте наличие его элементов в меньшем векторе с помощью двоичного поиска.

Ответ №3:

Вместо сортировки рассмотрите возможность обмена памятью на время, создав хэш-набор из меньшего вектора, а затем зацикливаясь на большем векторе, проверяя наличие этих элементов, как предлагается здесь . Это было бы быстрее, чем сортировка и использование std::set_intersection .

Метки: