Как я могу эффективно определить, содержат ли два списка элементы, упорядоченные одинаково?

Question

У меня есть два упорядоченных списка одного и того же типа элемента, каждый из которых имеет не более одного элемента каждого значения (скажем, целых и уникальных чисел), но в остальном без ограничений (один может быть подмножеством другого, они могут быть полностью разделить или разделить некоторые элементы, но не другие).

Как мне эффективно определить, заказывает ли A какие-либо два предмета иначе, чем B? Например, если A имеет элементы 1, 2, 10, а B - элементы 2, 10, 1, свойство не будет содержать списки 1 до 10, а B перечисляет его после 10. 1, 2, 10 против 2, 10 , 5 будет вполне допустимым, однако, так как А вообще не упоминает 5, я не могу полагаться на какое-либо данное правило сортировки, общее для обоих списков.

Answer 1

Вы можете получить O (n) следующим образом. Сначала найдите пересечение двух множеств, используя хеширование. Во-вторых, проверьте, идентичны ли A и B, если вы рассматриваете только элементы с пересечения.

Answer 2

Общий подход: сохранить все значения и их позиции в B как ключи и значения в HashMap. Переберите значения в A и найдите их в HashMap B, чтобы получить их позицию в B (или ноль). Если эта позиция до наибольшего значения позиции, которое вы видели ранее, то вы знаете, что что-то в 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;
}

Answer 3

Мой подход заключается в том, чтобы сначала сделать отсортированные копии 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

Наконец, сортируйте shared по его первому элементу (позиция в A) и проверяйте, чтобы всеего вторые элементы (позиции в 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) .