Сравните два массива или arraylists, найдите подобные и различные значения
У меня есть два массива (или arraylists, если это легче) строк. Я должен сравнить их, найти, которые только существуют в первом массиве, которые существуют в обоих, и которые только существуют во втором массиве. Эти массивы являются различными длинами и могут быть в различных заказах. При необходимости я предполагаю, что мог отсортировать их...
Я знаю, что мог взломать это вместе, но я думаю, что это могло бы иметь довольно стандартное и эффективное / "лучшее" решение, и я - любопытные больше, чем что-нибудь.
Я использую c# для этого, но если Вы хотите записать свое решение на другом языке, любая справка приветствуется.
Спасибо за справку!
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;
Если массивы большие, вы захотите использовать структуру данных, которая эффективна для этих операций; массивов нет.
Наивное решение - O (n ^ 2) по времени, если массивы имеют размер n.
Если вы отсортируете массивы на месте, вы сможете выполнять двоичный поиск элементов в них; сортировка, вероятно, будет O (n lg n), и поиск n раз по цене lg n за поиск также будет O (n lg n) во времени.
Если вы сначала превратите каждый массив в HashSet , то вы сможете сделать это за O (n) раз и O (n) дополнительного места.