如何有效地确定两个列表是否包含以相同方式排序的元素？

Question

我有两个相同元素类型的有序列表,每个列表每个值最多只有一个元素(比如整数和唯一数字),但是没有限制(一个可能是另一个的子集,它们可能完全是分离的,或分享一些元素,但不分享其他元素).

如何有效地确定A是否以不同于B的方式订购任何两个项目？例如,如果A具有项目1,2,10和B项目2,10,1,则该属性将不会保持为A列表1在10之前但B列出在10之后.1,2,10 vs 2,10 ,5将是完全有效的,但是A根本没有提到5,我不能依赖于两个列表共享的任何给定的排序规则.

Answer 1

您可以按如下方式获得 O(n)。首先，使用散列找到两个集合的交集。其次，如果只考虑交集的元素，则测试 A 和 B 是否相同。