Сортировка списка в соответствии с порядком, определенным другим списком

Question

Как можно отсортировать элементы списка A , чтобы они следовали порядку другого (расширенного) списка B ?Предположим, что нет дубликатов.

Например, A может содержать [8 2 5 1], а B может содержать [5 6 9 8 7 4 1 2 3] и т. Д.Я хотел бы отсортировать A , чтобы стать [5 8 1 2]

Мне интересны способы сделать это эффективно и с хорошей сложностью во время выполнения.

Answer 1

Если B является надмножеством A , я просто скопировал бы A в хеш-таблицу, отсканировал B исоздать новый список, куда я вставляю каждый элемент из B , который содержится в хэш-таблице.Использует O (a) дополнительную память и O (b) время выполнения.

Answer 2

Вот несколько идей:

(В данных временных сложностях n - это размер A , а m - это размер B . Время сложности не упрощены.)

• Для каждого элемента в B выполните линейный поиск A , чтобы проверить, существует ли этот элемент в нем. Если это так, замените его первым элементом в A , который еще не был поставлен на место. Временная сложность: O (нм)
• То же, что и выше, но сначала поместите содержимое A в эффективную структуру поиска, чтобы избежать линейного поиска. Сложность по времени: O (n + m) в предположении, что O (1) поиск
• Сортировка B . Затем для каждого элемента в A найдите его индекс (который гарантированно существует) в пределах B , используя бинарный поиск. Запишите этот индекс во вспомогательный массив того же размера, что и A . Используйте этот массив индексов в качестве входных данных для компаратора, который сортирует A . Сложность времени: O ((m log m) + (n log n) + (n log n))