代码之家 › 专栏 › 技术社区 › CameronCoob

联合段算法

sorting algorithm

CameronCoob · 技术社区 · 6 年前

我们有一个正确段[a;b]的列表(a<=b)。
需要得到一个新的名单与联合部分,如果他们被跨越。
例如:[1;3],[2;4],[7;8]=>[1;4],[7;8]。
我有一个想法:首先我们列出边界列表,对于每个边界,我们知道它是左边界还是右边界,然后我们按边界值对其进行排序,然后按左边界或右边界(左边界优先)。
我们的想法是浏览一下这个列表,然后:
1)作为左边界,我们在第一次见面时
2)右边框的确定如下:
我们有一个counter=0,当我们遇到左边框,然后是++counter,当它是右边框,所以-counter,当counter==0时,我们取当前边框为右边框。
以此类推,直到列表结束
你觉得这个算法怎么样?也许还有别的想法?

1 回复 | 直到 6 年前

MBo 6 年前

是的,你的想法大体上是对的。更多算法描述:

为所有段端创建一个成对的数组 (a or b; aux = +1 for a, -1 for b)

按坐标排序数组
(使用) aux 如果是平手,则作为第二个键:如果触碰的部分不应合并,则将-1放在+1之前;如果触碰的部分不应合并,则反之亦然)

制作 Count = 0

遍历数组,添加 辅助的 到 Count

价值 伯爵 在每一个时刻对应于打开的段数

什么时候? 伯爵 变为非零,开放输出段
什么时候? 伯爵 变为零,关闭输出段

   (1, 5), (2,6)
array 
   (1; 1), (2; 1), (5;-1), (6;-1)
count 
0    1       2         1      0
     ^                        ^
    start                    end

推荐文章