Пересечение множеств

@DiZar · Регистрация: 31.05.2021

Студворк — интернет-сервис помощи студентам

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

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

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

Перепробовал несколько вариантов кодов, но не подходит. Подскажите, как прописать программу?

@dondublon · 31.05.2021, 17:13

Что пробовали? Опишите словами идею хотя бы одного.

@eaa · 31.05.2021, 17:23

алгоритм слияния примените

@Catstail · 31.05.2021, 17:26

Психологическое наблюдение: почему некоторые студенты, учащиеся и пр. используют глагол "прописать" применительно к программе? Прописывают лекарство или человека (по месту прописки

). А программы не прописывают, их пишут. Наверное, таким студентам программирование представляется черной магией...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def intersection(arr1,arr2):
    res=[]
    i1,i2=0,0
    while True:
        if i1>=len(arr1) or i2>=len(arr2):
            break
        if arr1[i1]==arr2[i2]:
            res.append(arr1[i1])
            i1+=1
            i2+=1
        elif arr1[i1]<arr2[i2]:
            i1+=1
        else:
            i2+=1
    return res
    
print(intersection([1,3,6,7,10,11,12],[8,9,10,11,12,13]))

@AlexMarkov · 31.05.2021, 17:55

Catstail, я конечно не настолько опытный как Вы) Catstail, ну хотел бы узнать, данное условие задачи при таком варианте будет выполнено или нет?

Сообщение от DiZar

Алгоритм должен иметь сложность O(len(A)+len(B)).

Python
1
2
def intersection(lst_1,lst_2):
    return sorted(list(set(lst_1)&set(lst_2)))

@eaa · 31.05.2021, 17:58

AlexMarkov, а какая тут сложность алгоритма?

@AlexMarkov · 31.05.2021, 18:01

eaa, сложность в "наихудшем случае"

надеюсь Catstail или др. , ответят поподробнее)

@eaa · 31.05.2021, 18:02

AlexMarkov, а самому посчитать?

@AlexMarkov · 31.05.2021, 18:04

eaa, совсем некогда) да и не знаю как быть с оператором пересечения множеств '&'.

@outoftime · 31.05.2021, 18:14

AlexMarkov, https://wiki.python.org/moin/TimeComplexity

Intersection s&t ... O(len(s) * len(t))

Ух ты, сам не ожидал

Добавлено через 4 минуты
AlexMarkov, то ли в С++, то ли в Python есть функция которая умееть сливать 2 отсортированых списка в один.

Добавлено через 3 минуты
AlexMarkov, heapq.merge()

Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.

@Catstail · 31.05.2021, 18:34

AlexMarkov, не обижайтесь, но это - незачет. Подобные решения я называю "изюм из булки"

Уже много раз высказывался по этому поводу: такие решения подменяют алгоритмическое мышление библиотечным вызовом.

@AlexMarkov · 31.05.2021, 18:41

Catstail, не сомневаюсь, ну не все алгоритмисты, чаще всего необходимо просто решить быстро поставленную задачу.
А так, интересно было бы просмотреть как оцениваются сложности алгоритмов при применении различных функций или методов
в одной инструкции.

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@DiZar 0 / 0 / 0 Регистрация: 31.05.2021 Сообщений: 1

	Пересечение множеств 31.05.2021, 17:06. Показов 5089. Ответов 11 Метки нет (Все метки) Есть следующее задание: Даны два списка, упорядоченных по возрастанию (каждый список состоит из различных элементов). Найдите пересечение множеств элементов этих списков, то есть те числа, которые являются элементами обоих списков. Алгоритм должен иметь сложность O(len(A)+len(B)). Решение оформите в виде функции Intersection(A, B). Функция должна возвращать список пересечения данных списков в порядке возрастания элементов. Модифицировать исходные списки запрещается. Перепробовал несколько вариантов кодов, но не подходит. Подскажите, как прописать программу? 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	31.05.2021, 17:13
	Что пробовали? Опишите словами идею хотя бы одного. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	31.05.2021, 17:23
	алгоритм слияния примените 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	31.05.2021, 17:58
	AlexMarkov, а какая тут сложность алгоритма? 0

@AlexMarkov 99 / 86 / 20 Регистрация: 10.09.2019 Сообщений: 708
	31.05.2021, 18:01
	eaa, сложность в "наихудшем случае" надеюсь Catstail или др. , ответят поподробнее) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	31.05.2021, 18:02
	AlexMarkov, а самому посчитать? 0

@AlexMarkov 99 / 86 / 20 Регистрация: 10.09.2019 Сообщений: 708
	31.05.2021, 18:04
	eaa, совсем некогда) да и не знаю как быть с оператором пересечения множеств '&'. 0

@Catstail Супер-модератор 38200 / 21132 / 4310 Регистрация: 12.02.2012 Сообщений: 34,738 Записей в блоге: 14
	31.05.2021, 18:34
	AlexMarkov, не обижайтесь, но это - незачет. Подобные решения я называю "изюм из булки" Уже много раз высказывался по этому поводу: такие решения подменяют алгоритмическое мышление библиотечным вызовом. 1

@AlexMarkov 99 / 86 / 20 Регистрация: 10.09.2019 Сообщений: 708
	31.05.2021, 18:41
	Catstail, не сомневаюсь, ну не все алгоритмисты, чаще всего необходимо просто решить быстро поставленную задачу. А так, интересно было бы просмотреть как оцениваются сложности алгоритмов при применении различных функций или методов в одной инструкции. 0