Какой лучший алгоритм для сравнения двух массивов, чтобы увидеть, имеют ли они одни и те же элементы?
Предположим, что дубликатов нет, члены могут быть в любом порядке и что ни один из них не сортируется.
compare(
[a, b, c, d],
[b, a, d, c]
) ==> true
compare(
[a, b, e],
[a, b, c]
) ==> false
compare(
[a, b, c],
[a, b]
) ==> false
Очевидные ответы:
Какой из них вы используете, будет зависеть от того, можете ли вы сначала отсортировать списки и есть ли у вас хороший алгоритм хеширования.
Вы можете загрузить его в хеш-таблицу, отслеживая, сколько у нее элементов. Затем сверните на вторую, проверяя, находится ли каждый из ее элементов в хеш-таблице и подсчитывает, сколько элементов она имеет. Если каждый элемент во втором массиве находится в хэш-таблице, а две длины совпадают, то они одинаковы, иначе они не совпадают. Это должно быть O (N).
Чтобы сделать эту работу при наличии дубликатов, проследите, сколько из каждого элемента было замечено. Увеличение при циклическом перемещении по первому массиву и уменьшение во время цикла по второму массиву. Во время цикла над вторым массивом, если вы не можете найти что-либо в хэш-таблице или если счетчик уже равен нулю, они неравны. Также сравните общее количество баллов.
Другим методом, который работал бы при наличии дубликатов, является сортировка обоих массивов и линейное сравнение. Это должно быть O (N * log (N)).
Предполагая, что вы не хотите нарушать исходные массивы и пространство, рассматривается другое решение O (n.log(n)), которое использует меньше места, чем сортировка обоих массивов:
Если вы используете этот подход, воспользуйтесь библиотечной программой для выполнения двоичного поиска. Двоичный поиск удивительно подвержен ошибкам в ручном коде.
[Добавлено после просмотра решений, предлагающих поиск словаря/набора/хэша:]
На практике я бы использовал хэш. Несколько человек утверждают поведение O (1) для хэшей, что приводит к выводу, что решение на основе хэша равно O (N). Типичные вставки/поиски могут быть близки к O (1), а некоторые схемы хэширования гарантируют наихудший поиск O (1), но наихудшая вставка - при построении хэша - не O (1). Учитывая какую-либо конкретную структуру данных хэширования, будет некоторый набор ресурсов, которые могут вызвать патологическое поведение. Я подозреваю, что существуют структуры хэширования данных с объединенным наихудшим случаем для [insert-N-элементов, а затем - N-элементов] для O (N.log(N)) и O (N) -пространства.
Вы можете использовать подпись (коммутативную операцию над элементами массива) для дальнейшей оптимизации в случае, когда массив обычно отличается, сохраняя o(n log n) или распределение памяти.
Подпись может быть в виде фильтра (ов) цветения или даже простой коммутативной операции, такой как сложение или xor.
Простой пример (предполагая, что длинная сторона подписи и gethashcode как хороший идентификатор объекта, если объекты являются, скажем, ints, то их значение является лучшим идентификатором, а некоторые подписи будут длиннее)
public bool MatchArrays(object[] array1, object[] array2)
{
if (array1.length != array2.length)
return false;
long signature1 = 0;
long signature2 = 0;
for (i=0;i<array1.length;i++) {
signature1=CommutativeOperation(signature1,array1[i].getHashCode());
signature2=CommutativeOperation(signature2,array2[i].getHashCode());
}
if (signature1 != signature2)
return false;
return MatchArraysTheLongWay(array1, array2);
}
где (используя операцию добавления, при необходимости используйте другую коммутативную операцию, например, фильтры цветения)
public long CommutativeOperation(long oldValue, long newElement) {
return oldValue + newElement;
}
Это можно сделать по-разному:
1 - Грубая сила: для каждого элемента в массиве 1 проверьте, существует ли элемент в массиве2. Обратите внимание, что для этого потребуется отметить позицию/индекс, чтобы дубликаты могли обрабатываться надлежащим образом. Для этого требуется O (n ^ 2) с очень сложным кодом, даже не думайте об этом вообще...
2 - Сортируйте оба списка, затем проверьте каждый элемент, чтобы узнать, идентичны ли они. O (n log n) для сортировки и O (n) для проверки в основном O (n log n), сортировка может выполняться на месте, если беспорядок в массивах не является проблемой, если нет необходимости иметь память размером 2n для копирования отсортированного списка.
3 - добавьте элементы и подсчитайте их из одного массива в хеш-таблицу, затем выполните итерацию по другому массиву, проверив, что каждый элемент находится в хеш-таблице, и в этом случае счетчик декремента, если он не равен нулю, в противном случае удаляет его из хеш-таблицы. O (n) для создания хэш-таблицы и O (n) для проверки других элементов массива в хэш-таблице, поэтому O (n). Это вводит хэш-таблицу с максимальной памятью для n элементов.
4 - Лучший из лучших (среди вышеперечисленных): вычитайте или разделите каждый элемент в том же индексе двух массивов и, наконец, подведите итоговые значения. Например, A1 = {1,2,3}, A2 = {3,1,2} Diff = {- 2,1,1} теперь суммируют Diff = 0, что означает, что они имеют одинаковый набор целых чисел. Для этого подхода требуется O (n) без дополнительной памяти. Код С# выглядит следующим образом:
public static bool ArrayEqual(int[] list1, int[] list2)
{
if (list1 == null || list2 == null)
{
throw new Exception("Invalid input");
}
if (list1.Length != list2.Length)
{
return false;
}
int diff = 0;
for (int i = 0; i < list1.Length; i++)
{
diff += list1[i] - list2[i];
}
return (diff == 0);
}
4 вообще не работает, это худший
Если элементы массива заданы как разные, тогда XOR (побитовое XOR) все элементы обоих массивов, если ответ равен нулю, то оба массива имеют одинаковый набор чисел. Сложность времени равна O (n)
Я бы предложил сначала использовать сортировку и отсортировать сначала. Затем вы сравните первый элемент каждого массива, затем второй и т.д.
Если вы обнаружите несоответствие, вы можете остановиться.
Если вы сначала отсортируете оба массива, вы получите O (N log (N)).
Что такое "лучшее" решение, очевидно, зависит от того, какие ограничения у вас есть. Если это небольшой набор данных, сравнение сортировки, хэширования или грубой силы (например, nickf опубликовано) все будет очень похоже. Поскольку вы знаете, что имеете дело с целыми значениями, вы можете получить время сортировки O (n) (например, сортировка по методу radix), а хэш-таблица также будет использовать время O (n). Как всегда, есть недостатки для каждого подхода: сортировка потребует дублирования данных или деструктивного сортировки вашего массива (потеря текущего заказа), если вы хотите сэкономить место. У хэш-таблицы, очевидно, будет нехватка памяти для создания хеш-таблицы. Если вы используете метод nickf, вы можете сделать это с небольшими издержками памяти, но вам нужно иметь дело с O (n 2). Вы можете выбрать, что лучше для ваших целей.
Идти в глубокие воды здесь, но:
Отсортированные списки
сортировка может быть O(nlogn), как указано. просто чтобы уточнить, не имеет значения, что есть два списка, потому что: O(2*nlogn) == O(nlogn), тогда сравнение каждого элемента - это другое O (n), поэтому сортировка, то и сравнение каждого элемента - O (n) + O (nlogn), который: O(nlogn)
Хэш-таблицы:
Преобразование первого списка в хэш-таблицу - это O (n) для чтения + стоимость хранения в хеш-таблице, которая, как я полагаю, может быть оценена как O (n), дает O (n). Затем вам нужно будет проверить существование каждого элемента в другом списке в полученной хеш-таблице, которая (по крайней мере?) O (n) (при условии, что проверка существования элемента хэш-таблицы является постоянной). В целом, мы получаем O(n) для проверки.
Интерфейс Java-списка определяет equals, поскольку каждый соответствующий элемент равен.
Интересно, что определение интерфейса Java Collection почти не позволяет реализовать функцию equals().
Наконец, Java Устанавливает интерфейс на документацию, реализует это поведение. Реализация должна быть очень эффективной, но в документации нет упоминания о производительности. (Не удалось найти ссылку на источник, возможно, строго лицензирован. Загрузите и посмотрите на нее самостоятельно. Она поставляется с JDK). Рассматривая источник, HashSet (который является широко используемой реализацией Set) делегирует равные() в AbstractSet, который использует функцию containsAll() AbstractCollection, используя функцию contains() снова из hashSet. Итак, HashSet.equals() работает в O (n), как и ожидалось. (зацикливание всех элементов и поиск их в постоянном времени в хэш-таблице.)
Пожалуйста, отредактируйте, если вы знаете лучше, чтобы избавить меня от утомления.
Псевдокод:
A:array
B:array
C:hashtable
if A.length != B.length then return false;
foreach objA in A
{
H = objA;
if H is not found in C.Keys then
C.add(H as key,1 as initial value);
else
C.Val[H as key]++;
}
foreach objB in B
{
H = objB;
if H is not found in C.Keys then
return false;
else
C.Val[H as key]--;
}
if(C contains non-zero value)
return false;
else
return true;
Лучшим способом, вероятно, является использование hashmaps. Поскольку вставка в хэш-карту является O (1), построение хэш-карты из одного массива должно принимать O (n). Затем у вас есть n поисковых запросов, каждый из которых принимает O (1), а также другую операцию O (n). В общем, это O (n).
В python:
def comparray(a, b):
sa = set(a)
return len(sa)==len(b) and all(el in sa for el in b)
Игнорируя встроенные способы сделать это на С#, вы можете сделать что-то вроде этого:
Его O (1) в лучшем случае O (N) (по списку) в худшем случае.
public bool MatchArrays(object[] array1, object[] array2)
{
if (array1.length != array2.length)
return false;
bool retValue = true;
HashTable ht = new HashTable();
for (int i = 0; i < array1.length; i++)
{
ht.Add(array1[i]);
}
for (int i = 0; i < array2.length; i++)
{
if (ht.Contains(array2[i])
{
retValue = false;
break;
}
}
return retValue;
}
При столкновении в большинстве случаев хэш-карта является O (n), поскольку для хранения коллизий используется связанный список. Тем не менее, есть более эффективные подходы, и вы вряд ли столкнетесь с конфликтами, потому что если вы сделали хэш-карту, это было бы бесполезно. Во всех регулярных случаях это просто O (1). Кроме того, у него вряд ли будет больше, чем небольшое количество коллизий в одном хэш-карте, поэтому производительность не будет сосать это плохо; вы можете с уверенностью сказать, что это O (1) или почти O (1), потому что n настолько мало, что его можно игнорировать.
Вот еще один вариант, дайте мне знать, что вы, ребята, думаете. В худшем случае должно быть T (n) = 2n * log2n → O (nLogn).
private boolean compare(List listA, List listB){
if (listA.size()==0||listA.size()==0) return true;
List runner = new ArrayList();
List maxList = listA.size()>listB.size()?listA:listB;
List minList = listA.size()>listB.size()?listB:listA;
int macthes = 0;
List nextList = null;;
int maxLength = maxList.size();
for(int i=0;i<maxLength;i++){
for (int j=0;j<2;j++) {
nextList = (nextList==null)?maxList:(maxList==nextList)?minList:maList;
if (i<= nextList.size()) {
MatchingItem nextItem =new MatchingItem(nextList.get(i),nextList)
int position = runner.indexOf(nextItem);
if (position <0){
runner.add(nextItem);
}else{
MatchingItem itemInBag = runner.get(position);
if (itemInBag.getList != nextList) matches++;
runner.remove(position);
}
}
}
}
return maxLength==macthes;
}
public Class MatchingItem{
private Object item;
private List itemList;
public MatchingItem(Object item,List itemList){
this.item=item
this.itemList = itemList
}
public boolean equals(object other){
MatchingItem otheritem = (MatchingItem)other;
return otheritem.item.equals(this.item) and otheritem.itemlist!=this.itemlist
}
public Object getItem(){ return this.item}
public Object getList(){ return this.itemList}
}
Лучшее, о чем я могу думать, это O (n ^ 2), я думаю.
function compare($foo, $bar) {
if (count($foo) != count($bar)) return false;
foreach ($foo as $f) {
foreach ($bar as $b) {
if ($f == $b) {
// $f exists in $bar, skip to the next $foo
continue 2;
}
}
return false;
}
return true;
}