时间戳

首页 > 解决方案 > 在 C++ 中计算属于两个向量的元素数

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

问题描述

我们的任务是计算属于这两个列表的元素的数量。例如，对于列表

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

任何帮助，将不胜感激！

标签： c++vectorstltime-complexitystdvector

解决方案

你可以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
}

推荐阅读