Общие элементы между двумя списками, не использующими наборы в Python

Question

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

a=[2,2,1,1]
b=[1,1,3,3]

набор (а) и набор (б) работы
а & б не работают

Можно сделать это без набора и диктофона?

Answer 1

В Python 3.x (и Python 2.7, когда он будет выпущен), вы можете использовать collection.Counter для этого:

>>> from collections import Counter
>>> list((Counter([2,2,1,1]) & Counter([1,3,3,1])).elements())
[1, 1]

Вот альтернативный вариант использования collection.defaultdict (доступно в Python 2.5 и более поздних версиях). У него есть приятное свойство: порядок результата является детерминированным (по сути, он соответствует порядку второго списка).

from collections import defaultdict

def list_intersection(list1, list2):
    bag = defaultdict(int)
    for elt in list1:
        bag[elt] += 1

    result = []
    for elt in list2:
        if elt in bag:
            # remove elt from bag, making sure
            # that bag counts are kept positive
            if bag[elt] == 1:
                del bag[elt]
            else:
                bag[elt] -= 1
            result.append(elt)

    return result

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

Answer 2

Использование наборов является наиболее эффективным, но вы всегда можете сделать r = [i for i in l1 if i in l2].

Answer 3

SilentGhost, Марк Дикинсон и Ло'орис правы, большое спасибо за сообщение об этой проблеме - мне нужна общая часть списков, поэтому для:

а = [1,1,1,2]

б = [1,1,3,3]

результат должен быть [1,1]

Извините за комментарий в неподходящем месте - я зарегистрировался сегодня.

Я изменил твои решения:

def count_common(l1,l2):
        l2_copy=list(l2)
        counter=0
        for i in l1:
            if i in l2_copy:
                counter+=1
                l2_copy.remove(i)
        return counter

l1=[1,1,1]
l2=[1,2]
print count_common(l1,l2)

---

1