相关疑难解决方法(0)

问题

假设我有两个间隔集合,名为A和B.如何以最节省时间和内存效率的方式找到差异(相对补充)？

图片说明:

间隔时间点是整数(≤2 ¹²⁸ -1),他们总是两个2 ^ñ长排列的M×2 ^ñ晶格(这样就可以使一个二叉树了出来).

间隔可以在输入中重叠,但这不会影响输出(如果平坦的结果相同,则结果).

问题是因为两个集合中都有多个间隔(最多100,000,000),所以天真的实现可能会很慢.

从两个文件中读取输入,并按照这样的方式对输入进行排序:较小的子间隔(如果重叠)紧接在父项之​​后按大小顺序排列.例如:

[0,7]
[0,3]
[4,7]
[4,5]
[8,15]
...

我试过了什么？

到目前为止,我一直致力于生成二进制搜索树的实现,同时聚合[0,3],[4,7] => [0,7]两个集合中的相邻interval(),然后遍历第二个树并"碰撞"两个中存在的间隔(细分更大的必要时在第一个树中的间隔).

虽然这似乎适用于小型集合,但它需要越来越多的RAM来保存树本身,更不用说完成从树中插入和删除所需的时间.

我认为,由于间隔是预先排序的,我可以使用一些动态算法并在一次通过中完成.但是,我不确定这是否可行.

那么,我将如何以有效的方式解决这个问题呢？

免责声明:这不是作业,而是对我所面临的实际现实问题的修改/概括.我用C++编程,但我可以接受任何[命令式]语言的算法.

如何在c ++中为tr1 :: unordered_set类型的集合做交集和并集？我找不到太多关于它的参考.

任何参考和代码将受到高度赞赏.非常感谢你.

更新:我只是猜到了tr1 :: unordered_set应该提供交集,联合,差异的函数.因为那是集合的基本操作.当然我可以自己编写一个函数,但我只是想知道是否有来自tr1的内置函数.非常感谢你.

可能重复:
两个排序数组的交集

我们有两个排序的数组A和B,除了比较一个与其他数组中的所有元素之外,如何设计一个最佳的算法来找到具有它们共同元素的数组？

从这个，我们知道要解决两个排序的数组的交叉方法。那么如何得到多个排序数组的交集呢？

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

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 …