Сравните два массива или массива, найдите похожие и разные значения

Question

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

Я знаю, что смогу взломать это вместе, но я думаю, что это может быть довольно стандартным и эффективным / "лучшим" решением, и мне любопытно больше всего.

Я использую c # для этого, но если вы хотите написать свое решение на другом языке, любая помощь приветствуется.

Спасибо за помощь!

Answer 1

Если массивы большие, вам нужно использовать структуру данных, которая эффективна для этих операций;массивы не являются.

Наивным решением является O (n ^ 2) во времени, если массивы имеют размер n.

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

Если вы превратите каждый массив в HashSet<T>сначала вы можете сделать это за O (n) время и O (n) дополнительное пространство.

Answer 2

var onlyinfirst = from s in list1 where !list2.Contains(s) select s;
var onlyinsecond = from s in list2 where !list1.Contains(s) select s;
var onboth = from s in list1 where list2.Contains(s) select s;