оптимальный способ нахождения различий между двумя наборами - PullRequest
Новая
       19

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

0 голосов
/ 12 марта 2012

У меня есть два набора элементов, и я хочу, чтобы оптимальный алгоритм нашел их различия или в математической форме: A U B - A & cap; B

Один способ, которым я думал, это 

Bfound=0;
for (1->Na,i)
{
 flag=0;
 for (1->Nb,j)
 {
  if(A[i]==B[j])
  {
   flag=1;
   Bfound[j]=1;
  }

 }
 if (flag==0)
 print A[i]
}

for(1->Nb,i)
{
  if(Bfound[i]==0)
  print B[i]
}

Это оптимально?

Ответы [ 2 ]

3 голосов
/ 12 марта 2012

Чтобы ответить на ваш вопрос - нет, это не оптимально. Сложность вашего решения - время O (нм), где n и m - размеры A и B соответственно. Вы можете улучшить это время до O (nlogn + mlogm), если n ~ m.

  1. Сортировка обоих массивов за n log n + m log m раз.

  2. Найти пересечение за n+m время: 

    i = 0; 
j = 0;
while(i < n && j < m) {
  if (A[i] == B[j]) {
    print(A[i]);
    i++;
    j++;
  } else if (A[i] < B[j]) {
    i++;
  } else {
    j++;
  } 
}
1 голос
/ 12 марта 2012

Симметричная разность: A∪B - A∩B т.е. возвращает новый набор с элементами либо в A, либо в B, но не в обоих.Прямой способ из определения: 

# result = A ^ B
result = set() # start with empty set

# add all items that are in A but not in B
for item in A: # for each item in A; O(|A|), where |A| - number of elements in A
    if item not in B: # amortized O(1) (for hash-based implementation)
       result.add(item) # amortized O(1) (for hash-based implementation)

# add all items that are in B but not in A
for item in B:
    if item not in A:
       result.add(item)

Сложность O(|A|+|B|).

В C ++ тип - unordered_set, в Java, C # - HashSet, в Python -set.

Другой подход ( используемый в Python ) состоит в том, чтобы скопировать A в результат, а затем попытаться удалить B элементов из результата: 

# result = A ^ B
result = set(A) # copy A into result
for item in B:
    try: result.remove(item) # O(1)
    except KeyError: # item was not in the result
        result.add(item) # add previously not-found item

СложностьO(|A|+|B|).

...