arrays - 有效地合并相邻 block

Question

这就是我想要做的: 我有一个名为 merge() 的例程，它会定期被调用。它的任务是合并称为“Block”的数据结构，其内容是由“s_idx”和“e_idx”表示的整数范围，分别表示起始索引和结束索引。相邻 block 是其范围可以组合成新的连续范围的 block 。例如，范围为 (25,32) 的 block 3 和范围为 (33,40) 的 block 4 是相邻的，因此可以组合它们的范围以产生新的连续范围 (25,40)。所以最后，将只剩下一个 block ，将所有单独的 block 组合起来产生范围 (0,N-1)，其中 N 是 block 的总数。

我的问题是:是否有任何有效的算法来执行这样的操作？

当前的实现使用 O(N^2) 算法，随着 block 数的增加，速度会急剧下降。

for( int i=0 ; i<_merge_list.max()-1 ; i++ )
    {
        for( int j=i+1 ; j<_merge_list.max() ; j++ )
        {
            if( _merge_list.exist(i) && _merge_list.exist(j) )
            {
                if( _merge_list[i]->get_end_idx() + 1 ==    _merge_list[j]->get_start_idx() )
                {
                    _merge_list[i]->set_end_idx( _merge_list[j]->get_end_idx() );
                    _merge_list[i]->set_link( _merge_list[j]->get_block_idx() );


                                    perform(_merge_list[i]);

                    _merge_list.remove(j);          
                }
            }
        }

    }   

Answer 1

是否保证所有 block 都是连续的？如果是这种情况，那么在 O(N) 时间内找到最小、最大索引然后创建一个最终 block 应该是微不足道的，否则你可以先对 block 进行排序然后合并 O(NlogN) + O(N) = O(NlogN)

如果以有序的方式维护 block ，那么合并一个 block 只需要O(N)的时间。如果你一次拥有它们，那么你首先对 block 数组进行排序，然后合并。如果您将它们零碎地获取，您将以保持排序顺序的方式合并到 block 数组中。