多个排序数组的交集 [英] The intersection of multiple sorted arrays

问题描述

从此，我们知道了解决两个问题的交集的方法排序数组。那么如何获得多个排序数组的交集呢？

From this, we know the method to solve the intersection of two sorted arrays. So how to get the intersection of multiple sorted arrays?

基于两个排序数组的答案，我们可以将其应用于多个数组。这是代码

Based on the answers of two sorted arrays, we can apply it to multiple arrays. Here are the codes

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

是否有更好的解决方法？

Update1

从这两个主题中 1 和 2 中，似乎哈希集是更有效的方法。

From those two topics 1 and 2, it seem that Hash set is more efficient method to do that.

Update2

为提高性能，也许 min-heap 代替 vec_pos 。变量 max_val 保存所有向量的当前最大值。因此，只需将根值与 max_val 进行比较，如果它们相同，则可以将该元素放入交点列表。

To improve the performance, maybe the min-heap can be used instead of vec_pos in my codes above. And the variable max_val holds the current max value of all vectors. So just compare the root value with max_val, if they are same, this element can be put into intersection list.

推荐答案

要获取两个排序范围的交集，请 std :: set_intersection 可以使用：

To get the intersection of two sorted ranges, std::set_intersection can be used:

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

这比您的解决方案干净得多，解决方案过于混乱，无法检查正确性。
它还具有最佳的复杂性。

This looks a lot cleaner than your solution which is too confusing to check for correctness. It also has optimal complexity.

标准库算法 set_intersection 可以通过以下任何方式实现：使用

The standard library algorithm set_intersection may be implemented in any way that uses

最多进行2·（N1 + N2-1）个比较，其中N1 = std :: distance（first1，last1）和N2 = std :: distance（first2，last2）。

at most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2).

first1 等。是定义输入范围的迭代器。如果标准库是开源的（例如libstd ++或libc ++），则可以在标准库的源代码中查看其实际实现。

first1 etc. are the iterators defining the input ranges. You can check out the actual implementation in the source code of your standard-library if it is open source (like libstd++ or libc++).

这篇关于多个排序数组的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！