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

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

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

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

Answer 2

Вот другой вариант, дайте мне знать, что вы, ребята, думаете. Это должно быть 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 3

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

Answer 4

Игнорируя встроенные способы сделать это в 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 5

Лучший способ, вероятно, использовать хеш-карты. Поскольку для вставки в хэш-карту используется значение 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 6

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