Найти пересечение списков, которые содержат разные типы элементов. При этом не используя встроенные методы работы со списками. Python

Question

l1 = [3, 0, 8, 7.2, 'r', 3, True, [8, 2], 0.22, 'ee', 'r']
l2 = [3, 4, 6, 'r', 7.2, 33, 3, 0.22, 'r', 'r', [8, 2]]
`Результат должен быть`
[3, 3, 7.2, 'r', 'r', [8, 2], 0.22]
`Элементы могут идти в любом порядке`

`Был вот такой вариант, но препод его принял, т.к. "слишком слишком много циклов" `
c = []
count_a = 0
count_b = 0
for i in a:
    if i in c:
        continue
    for j in b:
        if i == j:
            for u in a:
                if i == u:
                    count_a += 1
            for u in b:
                if i == u:
                    count_b += 1
            count = min(count_a, count_b)
            for _ in range(count):
                c += [i]
                count_a = 0
                count_b = 0
            break

Есть идея. Разбить списки по типам, отсортировать их, отдельно каждые подравнивать, и слепить обратно. Препод сказал, что можно использовать функцию del, но я хз где тут ее можно всунуть. Также нельзя забывать о том, что если в l1 есть 2 одинаковых елем. и в l2 они есть, то и на выходе в списке должны быть 2 это елем. Пожалуйста помогите, а то

Answer 1

задача O(n^2):

идете по первому списку
находите во втором первый одинаковый элемент и
заносите его в новый список
удаляете его из второго

код:

l1 = [3, 0, 8, 7.2, 'r', 3, True, [8, 2], 0.22, 'ee', 'r']
l2 = [3, 4, 6, 'r', 7.2, 33, 3, 0.22, 'r', 'r', [8, 2]]

res = []

for src in l1:
    for dst_index in range(len(l2)):
        if src == l2[dst_index]:
            res.append(src)
            del(l2[dst_index])
            break

print(res)

Answer 2

В конце вопроса есть фраза "Разбить списки по типам, отсортировать их ...". То есть, списки разнотипные, но если в этих списках элементы одного типа, то они могут быть упорядочены - к ним можно применять операцию <. Разнотипные списки можно преобразовать в списки, которые можно сортировать даже если типы элементов различны:

def decorate(seq):
    return ((id(type(v)), v) for v in seq)

Идея в том чтобы элементы списков заменить на пары (число, элемент). Числа равны только для элементов одного типа. Такой список можно сортировать, при сравнении пар никогда не будут сравниваться элементы разных типов.

Для поиска общих элементов в списках (которые будем считать упорядоченными) нужна будет процедура, наподобие merge в алгоритме сортировки слиянием:

def intersect_iters(it1, it2):
    read1, read2 = True, True
    while True:
        if read1:
            try:
                v1 = next(it1)
            except StopIteration:
                return

        if read2:
            try:
                v2 = next(it2)
            except StopIteration:
                return

        if v1 < v2:
            read1, read2 = True, False
        elif v2 < v1:
            read1, read2 = False, True
        else:
            read1, read2 = True, True
            yield v1

Собирая всё вместе:

def decorate(seq):
    return ((id(type(v)), v) for v in seq)


def undecorate(seq):
    return (v[-1] for v in seq)


def intersect_iters(it1, it2):
    read1, read2 = True, True
    while True:
        if read1:
            try:
                v1 = next(it1)
            except StopIteration:
                return

        if read2:
            try:
                v2 = next(it2)
            except StopIteration:
                return

        if v1 < v2:
            read1, read2 = True, False
        elif v2 < v1:
            read1, read2 = False, True
        else:
            read1, read2 = True, True
            yield v1


def intersect(seq1, seq2):
    return undecorate(
        intersect_iters(
            iter(sorted(decorate(seq1))),
            iter(sorted(decorate(seq2)))
        )
    )


l1 = [3, 0, 8, 7.2, 'r', 3, True, [8, 2], 0.22, 'ee', 'r']
l2 = [3, 4, 6, 'r', 7.2, 33, 3, 0.22, 'r', 'r', [8, 2]]

print(list(intersect(l1, l2)))

$ python list_intersection.py 
[0.22, 7.2, [8, 2], 3, 3, 'r', 'r']

БЛОГ НА HUSL

Найти пересечение списков, которые содержат разные типы элементов. При этом не используя встроенные методы работы со списками. Python

Ответы (2 шт):