this中,我们知道了求解两个排序数组的交集的方法那么如何得到多个排序数组的交集呢?
基于两个排序数组的答案,我们可以将其应用于多个数组这是密码

vector<int> intersectionVector(vector<vector<int> > vectors){
    int vec_num = vectors.size();

    vector<int> vec_pos(vec_num);// hold the current position for every vector
    vector<int> inter_vec; // collection of intersection elements

    while (true){
        int max_val = INT_MIN;
        for (int index = 0; index < vec_num; ++index){
            // reach the end of one array, return the intersection collection
            if (vec_pos[index] == vectors[index].size()){
                return inter_vec;
            }

            max_val = max(max_val, vectors[index].at(vec_pos[index]));
        }

        bool bsame = true;
        for (int index = 0; index < vec_num; ++index){
            while (vectors[index].at(vec_pos[index]) < max_val){
                vec_pos[index]++; // advance the position of vector, once less than max value
                bsame = false;
            }
        }

        // find same element in all vectors
        if (bsame){
            inter_vec.push_back(vectors[0].at(vec_pos[0]));

            // advance the position of all vectors
            for (int index = 0; index < vec_num; ++index){
                vec_pos[index]++;
            }
        }
    }
}

有没有更好的解决办法?
更新1
12这两个主题来看,Hash set似乎是更有效的方法。
更新2
为了提高性能,也许可以在上面的代码中使用min-heap而不是vec_pos。变量max_val保存所有向量的当前最大值。因此只需将根值与max_val进行比较,如果它们相同,则可以将此元素放入交集列表中。

最佳答案

要获得两个排序范围的交集,可以使用std::set_intersection

std::vector<int> intersection (const std::vector<std::vector<int>> &vecs) {

    auto last_intersection = vecs[0];
    std::vector<int> curr_intersection;

    for (std::size_t i = 1; i < vecs.size(); ++i) {
        std::set_intersection(last_intersection.begin(), last_intersection.end(),
            vecs[i].begin(), vecs[i].end(),
            std::back_inserter(curr_intersection));
        std::swap(last_intersection, curr_intersection);
        curr_intersection.clear();
    }
    return last_intersection;
}

这看起来比你的解决方案要干净得多,因为你的解决方案太混乱,无法检查正确性。
它也具有最优的复杂性。
标准库算法set_intersection可以以任何使用
最多2个·(n1+n2-1)比较,其中n1=std::distance(first1,last1)和n2=std::distance(first2,last2)。
first1等是定义输入范围的迭代器。如果标准库是开源的(如libstd++或libc++),则可以在其源代码中查看实际实现。

关于c++ - 多个排序数组的交集,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25505868/

10-10 17:03