набор из объединения элементов, содержащихся в двух списках - PullRequest
Новая
       15

набор из объединения элементов, содержащихся в двух списках

0 голосов
/ 21 июля 2011

это для допроса перед интервью. я думаю, что у меня есть ответ, просто хотел получить подтверждение, что я прав.

Часть 1 - Скажите мне, что делает этот код, и его производительность big-O Часть 2 - Перепишите его сами и расскажите о производительности вашего решения в стиле big-O 

 def foo(a, b):
     """ a and b are both lists """
     c = []
     for i in a:
         if is_bar(b, i):
             c.append(i)
     return unique(c)

  def is_bar(a, b):
     for i in a:
         if i == b:
             return True
     return False

  def unique(arr):
     b = {}
     for i in arr:
         b[i] = 1

     return b.keys()

ОТВЕТЫ: Он создает набор из объединения элементов, содержащихся в двух списках. Это большая O производительность O (n2)

мое решение, которое, как я полагаю, достигает O (n) 

Set A = getSetA();
Set B = getSetB();

Set UnionAB = new Set(A);
UnionAB.addAll(B);

for (Object inA : a)
   if(B.contains(inA))
      UnionAB.remove(inA);

1 Ответ

1 голос
/ 21 июля 2011

Кажется, что оригинальный код делает пересечение, а не объединение.Он пересекает все элементы в первом списке (а) и проверяет, существует ли он во втором списке (б), и в этом случае он добавляет его в список с.Затем он возвращает уникальные элементы из c.Представление O (n ^ 2) кажется правильным.

...