我的数学不及格！我需要一种有效的方法将网络范围缩小为超集，例如如果我输入 IP 范围列表：
- 1.1.1.1至2.2.2.5
- 1.1.1.2至2.2.2.4
- 10.5.5.5至155.5.5.5
- 10.5.5.6至10.5.5.7
我想返回以下范围：
- 1.1.1.1至2.2.2.5
- 10.5.5.5至155.5.5.5
注意：输入列表没有排序（尽管它们可以排序？）。最简单的方法是检查列表中的每个范围，看看输入范围 x 是否是子集，如果是，则不插入范围 x。但是，每当您插入新范围时，它可能是现有范围的超集，因此您必须检查现有范围以查看它们是否可以折叠（例如，从我的列表中删除）。
这是段计算的并集。最佳算法（以 O(nlog(n)) 为单位）包括执行以下操作：
- 对列表 L 中的所有端点（起点和终点）进行排序（每个端点应该知道它所属的段）。如果端点等于起点，则应认为起点小于端点。
- 从左到右遍历排序列表L并维护数量LE-RE, where LE是您已经经过的左端点数量，并且RE是您已经经过的正确端点的数量。
- 每一次LE-RE达到零时，您位于段的连接并集的末尾，并且您知道您之前见过的段的并集（自上一次返回到零以来）是一个超集。
- 如果您还保留了每次返回到零之间的最小值和最大值，那么您就得到了超集的界限。
最后，您将获得不相交超集的排序列表。尽管如此，两个超集 A 和 B 可以是相邻的（A 的端点就在 B 的起点之前）。如果您希望合并 A 和 B，可以通过简单的后处理步骤或稍微修改步骤 3 来完成此操作：LE-RE达到零时，仅当 L 中的下一个元素不是当前元素的直接后继元素时，您才会认为它是超集的结尾。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
