Алгоритм, чтобы определить, имеют ли два массива одинаковые члены

Question

Каков наилучший алгоритм для сравнения двух массивов, чтобы узнать, имеют ли они одни и те же элементы?

Предположим, что дубликатов нет, члены могут быть в любом порядке и что ни один из них не сортируется.

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 

Answer 1

Очевидные ответы будут:

1. Сортировка оба списка, а затем проверить каждый элемент, чтобы увидеть, если они идентичны
2. Добавить элементы из одного массива в Hashtable, то перебирать другой массив, проверяя, что каждый элемент в хэш
итерационный алгоритм поиска
3. nickf в

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

Answer 2

Лучшее, что я могу представить, это 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; 
} 

Answer 3

Вы можете загрузить его в хеш-таблицу, отслеживая, сколько у нее элементов. Затем сверните на вторую, проверяя, находится ли каждый из ее элементов в хеш-таблице и подсчитывает, сколько элементов она имеет. Если каждый элемент во втором массиве находится в хэш-таблице, а две длины совпадают, то они одинаковы, иначе они не совпадают. Это должно быть O (N).

Чтобы сделать эту работу при наличии дубликатов, отследите, сколько из каждого элемента было замечено. Увеличение при циклическом перемещении по первому массиву и уменьшение во время цикла по второму массиву. Во время цикла над вторым массивом, если вы не можете найти что-либо в хэш-таблице или если счетчик уже равен нулю, они неравны. Также сравните общее количество баллов.

Другим методом, который работал бы в присутствии дубликатов, является сортировка обоих массивов и линейное сравнение. Это должно быть O (N * log (N)).

Answer 4

Я предлагаю сначала использовать сортировку и сортировать как первый. Затем вы сравните первый элемент каждого массива, затем второй и так далее.

Если вы обнаружили несоответствие, вы можете остановиться.

Answer 5

Если вы сначала отсортируете оба массива, вы получите O (N log (N)).

Answer 6

Лучший способ, вероятно, использовать hashmaps. Поскольку вставка в хэш-карту является O (1), построение хэш-карты из одного массива должно принимать O (n). Затем у вас есть n поисковых запросов, каждый из которых принимает O (1), а также другую операцию O (n). В общем, это O (n).

В питона:

def comparray(a, b): 
    sa = set(a) 
    return len(sa)==len(b) and all(el in sa for el in b) 

Answer 7

Игнорирование встроенный способов сделать это в C#, вы могли бы сделать что-то вроде этого:

Его 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; 
} 

Answer 8

Предполагая, что вы не хотите беспокоить оригинальных массивов и пространства является рассмотрение, другой O (n.log (п)) решение, которое использует меньше места, чем сортировка обоих массивов:

1. Возврат FALSE, если массивы различаются по размеру
2. сортировать первый массив - O (n.log (п)) времени, дополнительное пространство требуется размер одного массива
3. Для каждого элемента в 2-ом массиве, проверьте это в отсортированной копии первый массив, использующий двоичный поиск - O (n.log (n)) time

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

[Добавлено после рассмотрения решений, предполагающие словарь/набор/хэш-запросов:]

На практике я хотел бы использовать хэш. Несколько человек утверждают поведение O (1) для хэшей, что приводит к выводу, что решение на основе хэша равно O (N). Типичные вставки/поиски могут быть близки к O (1), а некоторые схемы хэширования гарантируют наихудший поиск O (1), но наихудшая вставка - при построении хэша - не O (1). Учитывая какую-либо конкретную структуру данных хэширования, будет некоторый набор ресурсов, которые могут вызвать патологическое поведение. Я подозреваю, что существуют хеширующие структуры данных с объединенным наихудшим случаем для [insert-N-элементов, а затем - N-элементов] O (N.log (N)) и O (N).

Answer 9

Что такое «лучшее» решение, очевидно, зависит от того, какие ограничения у вас есть. Если это небольшой набор данных, сравнение сортировки, хэширования или грубой силы (например, nickf) будет очень похоже. Поскольку вы знаете, что имеете дело с целыми значениями, вы можете получить время сортировки O (n) (например, сортировка по методу radix), а хэш-таблица также будет использовать время O (n). Как всегда, есть недостатки для каждого подхода: сортировка потребует дублирования данных или деструктивного сортировки вашего массива (потеря текущего заказа), если вы хотите сэкономить место. У хэш-таблицы, очевидно, будет нехватка памяти для создания хеш-таблицы. Если вы используете метод nickf, вы можете сделать это с небольшими накладными расходами памяти, но вам нужно иметь дело с O (n). Вы можете выбрать, что лучше для ваших целей.

Answer 10

Собираетесь в глубоких водах здесь, но:

отсортированных списков сортировки может быть O(nlogn) как было указано. просто для того, чтобы уточнить, не имеет значения, что существует два списка, потому что: O(2*nlogn) == O(nlogn), тогда сравнение каждого элемента - другое O (n), поэтому сортировка, то и сравнение каждого элемента - O (n) + O (nlogn), который: O(nlogn)

хэш-таблицы: Преобразование первого списка в хэш-таблице представляет собой о (п) для чтения + стоимость хранения в хэш-таблице, который я думаю можно оценить как O (N) , дает O (n). Затем вам нужно будет проверить существование каждого элемента в другом списке в полученной хеш-таблице, которая (по крайней мере?) O (n) (при условии, что проверка существования элемента хэш-таблицы является постоянной). Все в целом, мы закончили с O(n) для проверки.

Интерфейс Java-списка defines equals как у каждого соответствует элементам равным.

Интересно, что определение интерфейса Java Collection almost discourages implementing the equals() функция.

И, наконец, Java Set interface per documentation implements вот так. Реализация должна быть очень эффективной, но в документации нет упоминания о производительности. (Не удалось найти ссылку на источник, возможно, строго лицензирована. Загрузите и посмотрите на нее самостоятельно. Она поставляется с JDK). Рассматривая источник, HashSet (который является широко используемой реализацией Set) делегирует равные() в AbstractSet, который использует функцию containsAll() AbstractCollection, используя функцию contains() снова из hashSet. Итак, HashSet.equals() работает в O (n), как и ожидалось. (зацикливание всех элементов и поиск их в постоянное время в хэш-таблице.)

Пожалуйста, отредактируйте, если вы знаете, что лучше избавить меня от утомления.

Answer 11

При столкновении в большинстве случаев hashmap является O (n), потому что он использует связанный список для хранения коллизий. Тем не менее, есть более эффективные подходы, и вы вряд ли столкнетесь с конфликтами, потому что если вы сделали хэш-карту, это было бы бесполезно. Во всех регулярных случаях это просто O (1). Кроме того, у него вряд ли будет больше, чем небольшое количество коллизий в одном хэш-карте, поэтому производительность не будет сосать это плохо; вы можете смело сказать, что это O (1) или почти O (1), потому что n настолько мало, что его можно игнорировать.

Answer 12

Это можно сделать разными способами:

1 - Грубая сила: для каждого элемента в array1 проверить, что элемент существует в массив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 не работает вообще, это самый худший

Answer 13

Вы можете использовать подпись (коммутативной операции над членами массива) для дальнейшей оптимизации этого в случае, когда массив обычно отличается, сохраняя 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; 
} 

Answer 14

Вот еще один вариант, дай мне знать, что вы, ребята, think.It должен быть 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} 

}

Answer 15

Псевдокод:

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; 

Answer 16

Если элементы массива приведены в отличие, то XOR (побитовое исключающее ИЛИ) все элементы обоих массивов, если ответ ноль, то оба массива имеют одинаковый набор чисел. Сложность времени - O (n)