Вычислить количество элементов, принадлежащих обоим векторам в C ++

Question

Наша задача - рассчитать количество элементов, которые принадлежат обоим спискам. Например, для списков

vector<int> arr1{5,2,8,9}
vector<int> arr2{3,2,9,5}

Ответом будет 3, поскольку числа 2, 5 и 9 принадлежат обоим спискам. Я хочу сделать этот алгоритм с наименьшей временной сложностью - O (nlogn). Цель состоит в том, чтобы отсортировать список, а затем выполнить итерацию по обоим сразу и найти общие элементы.

Вот что у меня есть:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int counter;
    vector<int> arr1{ 5, 2, 8, 9 };
    vector<int> arr2{3, 2, 9, 5};

    sort(arr1.begin(), arr1.end()); // 2, 5, 8, 9
    sort(arr2.begin(), arr2.end()); // 2, 3, 5, 9

    for (int i = 0; i < 4; i++) {
        // insert code here
    }

    cout << counter;

    return 0;
}

Любая помощь будет цениться!

Answer 1

Вы можете использовать std::set_intersection как:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::vector<int> v2{ 5, 7, 9, 10 };
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> v_intersection;

    std::set_intersection(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(v_intersection)
    );

    std::cout << v_intersection.size() << std::endl; // output: 2
}

Answer 2

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

    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] == arr2[j]) {
            ++counter;
            ++i;
            ++j;
        }

        else if (arr1[i] < arr2[i]) {
            ++i;
        }

        else {
            ++j;
        }
    }

Я хочу, чтобы вы отметить, что для решения этой проблемы с использованием заданного пересечения ожидалось время O(n).

Answer 3

#include <bits/stdc++.h> 
using namespace std; 
#define MAX 100000 
bitset<MAX> bit1, bit2, bit3; 

// Function to return the count of common elements 
int count_common(int a[], int n, int b[], int m) 
{ 

    // Traverse the first array 
    for (int i = 0; i < n; i++) { 

        // Set 1 at position a[i] 
        bit1.set(a[i]); 
    } 

    // Traverse the second array 
    for (int i = 0; i < m; i++) { 

        // Set 1 at position b[i] 
        bit2.set(b[i]); 
    } 

    // Bitwise AND of both the bitsets 
    bit3 = bit1 & bit2; 

    // Find the count of 1's 
    int count = bit3.count(); 

    return count; 
} 

Попробуйте этот метод, чтобы решить проблему. Это в основном работает в O (log min (n, m));

Answer 4

Майкл указал мне, что это можно сделать в O(N). Вместо сортировки вы можете использовать два массива размера N. Пройдите по одному вектору, чтобы отметить элементы, которые в нем появляются, проделайте то же самое с другим вектором, затем просмотрите эти два массива, чтобы подсчитать элементы, которые появляются в обоих. Все отдельные шаги O(N), следовательно, в сумме это также O(N):

#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> v1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::vector<int> v2{ 5, 7, 9, 10 };

    auto m1 = std::minmax_element(v1.begin(),v1.end());
    auto m2 = std::minmax_element(v2.begin(),v2.end());

    auto min = std::max( *m1.first, *m2.first);  // we only need to consider the max minimum element
    auto max = std::min( *m1.second, *m2.second); // and the min maximum element

    auto get_occurence_vector = [min,max](const std::vector<int>& v) {
        std::vector<bool> result(max-min+1); // max and min included, hence +1
        for (const auto& e : v) {
            int t = e - min;
            if (t >= 0 && t <= max) result[t] = true;
        }
        return result;
    };

    auto occurs_in1 = get_occurence_vector(v1);
    auto occurs_in2 = get_occurence_vector(v2);

    size_t counter = 0;
    for (size_t i = 0;i< occurs_in1.size(); ++i) {
        if (occurs_in1[i] && occurs_in2[i]) {
            std::cout << i + min << "\n";
            ++counter;
        }
    }

    std::cout << "count = " << counter;
}

Вывод:

5
7
count = 2

По сути, это компромисс между сложностью во время выполнения и использование памяти. Если диапазон значений в векторах огромен, но их размер невелик, сортировка может быть более эффективной, даже если сложность хуже (помните, что сложность ограничена большим N).