如何高效地确定两个列表是否包含按相同顺序排序的元素？

Question

我有两个相同元素类型的有序列表，每个列表最多只有一个值的每个元素（例如整数和唯一数字），但除此之外没有任何限制（其中一个可能是另一个的子集，它们可能完全不相交，或者共享某些元素而不共享其他元素）。

如何有效地确定A是否以与B不同的方式对任何两个项进行排序？例如，如果A具有项目1、2、10，而B具有项目2、10、1，则该属性将不成立，因为A在10之前列出了1，但B在10之后列出了它。然而，1、2、10与2、10、5是完全有效的，因为A根本没有提到5，我不能依赖于任何给定的排序规则共享两个列表。

- SoftMemes

Answer 1

你可以按照以下步骤获得O(n)。首先，使用哈希查找两个集合的交集。其次，如果只考虑交集中的元素，则测试A和B是否相同。

- jonderry

---

这正是我所想的。对列表进行交集和比较。 - Chris

将列表转换为基于哈希的集合的时间复杂度为O(n)，将每个列表与其他列表的集合进行比较以形成仅包含重叠元素的列表的时间复杂度为O(n)，比较这些列表的时间复杂度为O(n)。太棒了！ - SoftMemes

Answer 2

我的方法是首先制作A和B的排序副本，这些副本还记录原始列表中元素的位置：

for i in 1 .. length(A):
    Apos[i] = (A, i)
sortedApos = sort(Apos[] by first element of each pair)

for i in 1 .. length(B):
    Bpos[i] = (B, i)
sortedBpos = sort(Bpos[] by first element of each pair)

现在使用标准列表合并记录A和B中共享元素的位置来查找这些共同的元素：

i = 1
j = 1
shared = []
while i <= length(A) && j <= length(B)
    if sortedApos[i][1] < sortedBpos[j][1]
        ++i
    else if sortedApos[i][1] > sortedBpos[j][1]
        ++j
    else    // They're equal
        append(shared, (sortedApos[i][2], sortedBpos[j][2]))
        ++i
        ++j

最后，按其第一个元素（在A中的位置）对shared进行排序，并检查其所有第二个元素（在B中的位置）是否递增。当且仅当A和B中共同的元素以相同的顺序出现时，才会出现这种情况：

sortedShared = sort(shared[] by first element of each pair)
for i = 2 .. length(sortedShared)
    if sortedShared[i][2] < sortedShared[i-1][2]
        return DIFFERENT

return SAME

时间复杂度：2*(O(n) + O(nlog n)) + O(n) + O(nlog n) + O(n) = O(nlog n)。

- j_random_hacker

Answer 3

一般方法：将B中所有值及其位置存储为HashMap中的键和值。在A中迭代值，并在B的HashMap中查找它们以获取它们在B中的位置（或null）。如果此位置在之前看到的最大位置值之前，则您知道B中的某些内容与A中的顺序不同。运行时间为O(n)。

粗略的、未经测试的代码：

boolean valuesInSameOrder(int[] A, int[] B)
{
  Map<Integer, Integer> bMap = new HashMap<Integer, Integer>();
  for (int i = 0; i < B.length; i++)
  {
    bMap.put(B[i], i);
  }

  int maxPosInB = 0;
  for (int i = 0; i < A.length; i++)
  {
    if(bMap.containsKey(A[i]))
    {
      int currPosInB = bMap.get(A[i]);
      if (currPosInB < maxPosInB)
      {
        // B has something in a different order than A
        return false;
      }
      else
      {
        maxPosInB = currPosInB;
      }
    }
  }

  // All of B's values are in the same order as A
  return true;
}

- Yevgeniy Brikman