在 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

答案很简单，因为数组是排序的，你可以在两个数组上有索引运行，当元素相等时计数，当一个小于另一个时递增。

    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 2

您可以像这样使用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 3

Michael 向我指出，可以在 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）。

Answer 4

#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));

在 C++ 中计算属于两个向量的元素数

Calculate Number of Elements that Belong in both Vectors in C++

c++

stl

vector

time-complexity

stdvector