Как получить необычные элементы из двух связанных списков?

Question

Даны два связанных списка целых чисел. Меня попросили вернуть связанный список, который содержит необычные элементы. Я знаю, как сделать это в O (n ^ 2), любой способ сделать это в O (n)?

Answer 1

Использовать хеш-таблицу.

Итерация по первому связанному списку, ввод значений, с которыми вы столкнулись, в хеш-таблицу.

Итерация по второму связанному списку, добавление любого не найденного элементав хеш-таблицу в список нечастых элементов.

Это решение должно быть O (n), при условии отсутствия коллизий в хеш-таблице.

Answer 2

создать новый пустой список. иметь хэш-таблицу и заполнить ее элементами обоих списков. сложность н. затем последовательно перебирайте каждый список и, перебирая, помещайте в новый список те элементы, которых нет в хеш-таблице сложность н. общая сложность = n

Answer 3

Если они не отсортированы, то я не верю, что возможно стать лучше, чем O (n ^ 2).Тем не менее, вы можете добиться большего успеха, сортируя их ... вы можете отсортировать их в достаточно быстрое время, а затем получить что-то вроде O (nlogn) (я не уверен, что это так, но я думаю, что это может быть так быстро, есливы используете правильный алгоритм).