计算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：

Answer 2

答案很简单，由于对数组进行了排序，因此您可以使索引在两个数组上运行，在元素相等时计数，在一个元素小于另一个元素时递增。

Answer 3

O(n)

Answer 4

Michael指出，可以在

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

中完成。可以使用大小为N的数组来进行排序，而不是进行排序。遍历一个向量以标记其中出现的元素，然后遍历另一个向量以查看数组中是否标记了其中的元素。所有单个步骤均为O(N)，因此总计也为O(N)：