什么是从对列表中提取行李的有效算法？

Question

我有一对对象列表.对象可以按任意顺序出现在对中.什么是最有效的算法(和实现？)来找到相同对象之间的所有包(即允许重复的集合).为了我的目的,可以假定对象引用是指针,或名称或一些类似的方便,简短,有用的表示.单个对是可识别的.在该对的两个部分中没有对具有相同的对象.

所以给出一对对列表(Oid是一个对象引用; Pid一对引用)

O1-P1-O2
O3-P2-O4
O5-P3-O1
O1-P4-O2
O2-P5-O1
O1-P6-O5
O7-P7-O8

应该返回:

P1;P4;P5 and P3;P6

Answer 1

花哨的术语可能会使这个问题看起来很难,但实际上很简单.

1. 每对中的订单元素.(既然你说对象可以表示为数字,我们pair.first <= pair.second总是假设)
2. 排序列表,使用传统方式比较对.即pair1 < pair2意味着pair1.first < pair2.first或pair1.first == pair2.first && pair1.second < pair2.second.

您的示例中的排序列表将如下所示

O1-P1-O2
O1-P4-O2
O1-P5-O2
O1-P3-O5
O1-P6-O5
O3-P2-O4
O7-P7-O8

现在,来自一个"包"的所有元素将占据列表中的连续点.来吧抓住他们.

还可以使用哈希来解决这个问题.