Сравните порядок двух списков

Question

Есть ли алгоритм лучше, чем O (n ^ 2) для переупорядочения Списка 2, чтобы он соответствовал Списку 1

Список 1: A B C D

Список 2: B D C A

примечание: список 2 может иметь больше, меньше или даже полностью отличаться от списка 1.

Answer 1

Если вы можете создать итоговый порядок для типов элементов в списках, то вы можете создать индекс для списка 1, отсортировав элементы.Затем вы можете использовать этот индекс для переупорядочения списка 2. Этот алгоритм имеет O (n log n) во времени и требует дополнительного O (n) в пространстве.

Answer 2

Вы ищете алгоритм * Diff !

Answer 3

Одна возможность, которая привела бы к O (n Log (n)), была бы следующей.Это требует чтения значений списка в массив / вектор / сортируемый тип структуры:

• Сортировка списка 1 по значению и сохранение информации о положении.Это позволяет быстро найти предмет и узнать его положение.Стоимость сортировки составляет O (n log n)
• Список сортировки 2, используя отсортированный список с первого шага в качестве функции сравнения.Два сравнивают два значения, ищут их в отсортированных результатах списка 1 и используют относительные позиции как сравнение между этими двумя значениями.Стоимость такого рода также O (n log n).

После редактирования вы упоминаете, что второй список может не иметь отношения к первому списку.Таким образом, функция сравнения должна учитывать это.Если одно или оба сравниваемых значения не указаны в первом списке, функции сравнения необходимо принять решение о порядке упорядочения значений (например, идут ли они в конце или в начале?).