Удаление общих элементов в двух списках за время сложности O (n)

Question

Предположим, что мои два списка:

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

, итоговый список должен быть

a1=[1,2,3]
b1=[4]

Пожалуйста, помогите

Answer 1

Вот как вы можете использовать понимание списков:

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

a1 = [v for i,v in enumerate(a) if v not in a[:i]]
b1 = [v for v in b if v not in a]

Вы можете использовать наборы, как в ответе Яна, но тогда вы не будете может извлекать элементы из массивов согласно индексации. Этот код сохраняет заказ.

Answer 2

Вы можете использовать set(), но это может не поддерживать порядок.

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

a1 = list( set(a) & set(b) )
b1 = list( set(a) ^ set(b) )

print(a1)
print(b1)

Answer 3

1. Построить вхождение элемента подсчета словаря
2. Найти разницу во вхождениях
3. Заполнить окончательные списки с разницей в вхождениях а. версия, которая не сохраняет порядок, просто повторяет разность элементов б. версия, которая сохраняет порядок, уменьшает счетчик для каждого вхождения и отфильтровывает элемент, если счетчик равен 0 или меньше (например: элемент '4' встречается 2 раза в a, но 3 раза в b, diff равен -1, не оставляйте никаких '4'. Но, если 6 раз и 3 раза, diff равно 3, оставьте 3x '4) .

Версия без сохранения порядка:

import collections

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

# element counter O(n)
ac = collections.Counter(a)
bc = collections.Counter(b)

# union of all keys in dict O(n)
keys = set(ac) | set(bc)
# get difference for all counters O(n)
diff = {k: ac.get(k,0)-bc.get(k,0) for k in keys}

a1 = []
b1 = []
# iterate over all keys O(n)
for k,v in diff.items():
    a1+=[k]*v
    b1+=[k]*-v
    # concatenate to lists, repeat element v times

print(a1,b1)

Версия с сохранением порядка:

import collections

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

# element counter O(n)
ac = collections.Counter(a)
bc = collections.Counter(b)

# get difference for all counters O(n)
diffa = {k: v-bc.get(k,0) for k,v in ac.items()}
diffb = {k: v-ac.get(k,0) for k,v in bc.items()}

a1 = []
b1 = []
# iterate over all keys O(n)
for x in a:
    if(diffa[x]>0):
      a1 += [x]
    diffa[x] -= 1

for x in b:
    if(diffb[x]>0):
        b1 += [x]
    diffb[x] -= 1

print(a1,b1)

Примечание: это требует высоких накладных расходов из-за сохранения сложности linear O (n) путем построения справочных таблиц (не говоря уже о сложности пространства). Это примерно около O (6n), так что выигрыш в производительности наблюдается только тогда, когда списки очень и очень большие. Для небольших списков, подобных примеру в OP, простое использование поиска «in» для каждого элемента будет быстрее, так как не нужно создавать таблицы поиска. Если это не проблема кодирования, вероятно, вам следует использовать другой подход к своим данным, иначе преимущество сложности здесь к вам не относится. Если это какая-то задача типа обработки больших данных, ваше узкое место, вероятно, будет заключаться в правильном использовании генераторов и буферизации / сегментации ввода-вывода, и в вашей структуре уже есть более эффективные методы для решения этих задач.

Answer 4

вы можете использовать простой, если проверяет, как указано ниже

a=[1,1,2,2,3,3]
b=[1,2,3,4]
x=[]
y=[]
for i in a:
    if i not in x:
        x.append (i)
for i in b:
    if i not in x and i not in y:
        y.append(i)
print(x,y)

Answer 5

Используйте для них sets(...) и -:

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

a, b = map(set, [a, b])
b = b - a
print(a, b)

Это дает

{1, 2, 3} {4}