Как сделать ввод множества пользователем из консоли?

Question

[n293]

Есть задачка:

Даны два списка, упорядоченных по возрастанию (каждый список состоит из различных элементов).

Найдите пересечение множеств элементов этих списков, то есть те числа, которые являются элементами обоих списков. Алгоритм должен иметь сложность O(len(A)+len(B)).

Решение оформите в виде функции Intersection(A, B). Функция должна возвращать список пересечения данных списков в порядке возрастания элементов. Модифицировать исходные списки запрещается.

Я решил ее как-то так:

def intersection(a, b):
    c = a.update(b)
    for i in c:
        return i

    # return c.difference_update(d)

numList1 = list(set(int, input().split()))
numList2 = list(set(int, input().split()))

print(intersection(numList1, numList2))

При запуске программы ввожу первое множество, жму энтер и выдает ошибку:

Traceback (most recent call last):
File "C:/Users/Николай/PycharmProjects/week6/Intersection of many.py", line 8, in
numList1 = list(set(int, input().split()))
TypeError: set expected at most 1 arguments, got 2

Как мне от этого уйти? Честно говоря не понимаю как решить задачку. Буду признателен за подсказки.

Answer 1

[Andrey Dugin]

Что за int в set()? Читайте, что написано в трейсе. И в чём смысл из списка, который возвращается функцией .split(), делать set, и снова list? Ну и вообще, Вы на каком языке пишете? С синтаксисом всё совсем плохо... Update списка, присвоение апдейта, return в цикле... Изучите матчасть всё-таки, не надо играть в угадайку.

UPD Вот решение, соответствующее всем условиям задачи:

def intersect(a1, a2):
    common = []
    i1, i2 = iter(a1), iter(a2)
    try:
        e1, e2 = next(i1), next(i2)
        while True:
            if e1 < e2:
                e1 = next(i1)
            elif e1 > e2:
                e2 = next(i2)
            else:
                common.append(e1)
                e1, e2 = next(i1), next(i2)
    except StopIteration:
        return common
    
intersect([1,2,3,4,5,10,12], [3,4,5,6,7,11,12])  # => [3, 4, 5, 12]

Answer 2

[n293]

Большое спасибо за помощь: Андрей Дугин и longclaps

Итоговое решение:

def intersection(a, b):
    c = a & b
    return sorted(c, key=int)

numList1 = set(input().split())
numList2 = set(input().split())

print(*intersection(numList1, numList2))

Comments

[Andrey Dugin]

Только у этого алгоритма сложность сильно меньше O(len(A)+len(B))

[n293]

Андрей Дугин, буду признателен, если объясните, как вычислить сложность алгоритма, ну либо ссылку на источник.

Это решение подходит под заданную сложность?

def intersection(a, b):
    result = list(set(a) & set(b))
    return result

numList1 = list(map(int, input().split()))
numList2 = list(map(int, input().split()))

print(*intersection(numList1, numList2))

[Andrey Dugin]

n293, Вам сюда: https://wiki.python.org/moin/TimeComplexity
Проверка x in set имеет сложность в среднем O(1), в худшем случае O(n).
По условию задачи имеется в виду проход по обоим спискам: x in list => O(n).