如何有效地确定两个列表是否包含以相同方式排序的元素?
我有两个相同元素类型的有序列表,每个列表的每个值最多有一个元素(例如整数和唯一数字),但除此之外没有任何限制(一个可能是另一个的子集,它们可能完全分离,或共享一些元素但不共享其他元素)。
如何有效地确定 A 订购任意两个商品的方式是否与 B 不同?例如,如果 A 有项目 1、2、10,B 有项目 2、10、1,则该属性不会成立,因为 A 将 1 列出在 10 之前,但 B 将其列出在 10 之后。 1, 2, 10 与 2, 10 , 5 是完全有效的,但是由于 A 根本没有提到 5,所以我不能依赖两个列表共享的任何给定排序规则。
I have two ordered lists of the same element type, each list having at most one element of each value (say ints and unique numbers), but otherwise with no restrictions (one may be a subset of the other, they may be completely disjunct, or share some elements but not others).
How do I efficiently determine if A is ordering any two items in a different way than B is? For example, if A has the items 1, 2, 10 and B the items 2, 10, 1, the property would not hold as A lists 1 before 10 but B lists it after 10. 1, 2, 10 vs 2, 10, 5 would be perfectly valid however as A never mentions 5 at all, I cannot rely on any given sorting rule shared by both lists.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
您可以按如下方式获得 O(n)。首先,使用散列找到两个集合的交集。其次,如果只考虑交集的元素,则测试 A 和 B 是否相同。
You can get O(n) as follows. First, find the intersection of the two sets using hashing. Second, test whether A and B are identical if you only consider elements from the intersection.
我的方法是首先制作
A
和B
的排序副本,它们还记录原始列表中元素的位置:现在使用标准列表合并查找这些共同元素记录共享元素在
A
和B
中的位置:最后,按第一个元素对
shared
进行排序(在A 中的位置
)并检查其所有第二个元素(B
中的位置)是否都在增加。如果A
和B
共有的元素以相同的顺序出现,就会出现这种情况:时间复杂度:2*(O(n) + O(nlog n)) + O(n) + O(nlog n) + O(n) = O(nlog n)。
My approach would be to first make sorted copies of
A
andB
which also record the positions of elements in the original lists:Now find those elements in common using a standard list merge that records the positions in both
A
andB
of the shared elements:Finally, sort
shared
by its first element (position inA
) and check that all its second elements (positions inB
) are increasing. This will be the case iff the elements common toA
andB
appear in the same order:Time complexity: 2*(O(n) + O(nlog n)) + O(n) + O(nlog n) + O(n) = O(nlog n).
一般方法:将 B 中的所有值及其位置作为键和值存储在 HashMap 中。迭代 A 中的值并在 B 的 HashMap 中查找它们以获取它们在 B 中的位置(或 null)。如果这个位置在您之前见过的最大位置值之前,那么您就知道 B 中的某些内容与 A 中的顺序不同。运行时间为 O(n) 。
粗糙的、完全未经测试的代码:
General approach: store all the values and their positions in B as keys and values in a HashMap. Iterate over the values in A and look them up in B's HashMap to get their position in B (or null). If this position is before the largest position value you've seen previously, then you know that something in B is in a different order than A. Runs in O(n) time.
Rough, totally untested code: