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

Ответ 1

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

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

Здесь альтернатива, использующая collections.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 в двух входных списках. Из вашего вопроса неясно, является ли это поведением, которое вы хотите.

Ответ 2

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

Ответ 3

SilentGhost, Mark Dickinson и Lo'oris правы, очень спасибо за сообщение об этой проблеме - мне нужна общая часть списков, поэтому для:

а = [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