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

你可以得到O(n)如下。首先,使用散列查找两个集合的交集。其次,如果只考虑交叉点的元素,测试A和B是否相同。

我的方法是先把 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)

现在使用一个标准的列表合并来查找这些共同的元素,该合并记录了两个元素的位置 一个 乙 共享元素的:

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

shared 通过它的第一个元素(位置 一个 )并检查其所有第二个元素(位置 )正在增加。如果这些元素 和 乙 以相同的顺序出现:

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(nlogn))+O(n)+O(nlogn)+O(n)= O(非直瞄)

一般方法:将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;
}