|
0 / 0 / 0
Регистрация: 24.09.2023
Сообщений: 3
|
||||||
Найти пары одинаковых значений из двух последовательностей24.09.2023, 16:59. Показов 709. Ответов 11
Всем привет, помогите оптимизировать код задачи.
Задача: У Никиты и Дианы день рождения в один день! Никите Ярик подарил последовательность целых чисел a1,a2,…,an - размера n , а Диане последовательность b1,b2,…,bm - размера m. Вообще, Никита и Диана во многом похожи – день рождения в один день, оба учатся в Петрозаводском Государственном Университете, оба участники Клуба Творчества Программистов. В связи с такими интересными фактами, они решили проверить вообще все в жизни пункты, по которым они между собой могут оказаться похожими. Начать они решили с подсчета похожести последовательностей, которые у них есть. Похожестью двух последовательностей назовем число пар чисел (i,j) таких, что (1≤i≤n), (1≤j≤m) и ai=bj. Поскольку Диане и Никите нужно проверить еще куча всего, в чем они могут быть похожими, им сейчас не до написания программ, и поэтому они обратились с этой задачей к Вам. Входные данные: В первой строке вам задано число n (1≤n≤2⋅105) — размер Никитиной последовательности. Во второй строке задана последовательность Никиты — a1,a2,…,an (1≤ai≤109). В третьей строке вам задано число m (1≤m≤2⋅105) — размер Дианиной последовательности. Во четвертой строке задана последовательность Дианы — b1,b2,…,bm (1≤bj≤109). Выходные данные: Выведите одно число — похожесть последовательности Дианы и Никиты. Пример: Входные данные: 6 1 2 3 4 5 6 4 4 5 6 7 Выходные данные: 3 Входные данные: 10 1 1 1 1 1 2 2 2 2 2 10 2 2 2 2 2 1 1 1 1 1 Выходные данные: 50 Я написал код, и не могу понять, как его можно ещё ускорить:
0
|
||||||
| 24.09.2023, 16:59 | |
|
Ответы с готовыми решениями:
11
Найти все пары одинаковых значений Найти все пары одинаковых значений среди 4х переменных Объединение двух последовательностей, сохраняя исходный порядок первой, при одинаковых элементах сортировка по второй |
|
|
||||||
| 24.09.2023, 17:19 | ||||||
0
|
||||||
|
Заблокирован
|
|||||||
| 24.09.2023, 17:27 | |||||||
0
|
|||||||
|
Модератор
13766 / 10960 / 6490
Регистрация: 18.12.2011
Сообщений: 29,234
|
||||||
| 24.09.2023, 17:29 | ||||||
|
А вот так попробуйте:
0
|
||||||
|
0 / 0 / 0
Регистрация: 24.09.2023
Сообщений: 3
|
||||
| 24.09.2023, 18:24 [ТС] | ||||
|
Ваше решение не работает на 2-м примере
На тесте 53 задачи, она валит из-за неверного ответа, в моем случае это было из-за того, что я использовал int, вместо long, я попробовал сделать на вашем решении тоже самое, но не помогло Ваше решение также неправильно работает со вторым примером
0
|
||||
|
677 / 479 / 216
Регистрация: 06.09.2013
Сообщений: 1,312
|
||||||
| 24.09.2023, 19:49 | ||||||
0
|
||||||
|
Заблокирован
|
|
| 24.09.2023, 19:52 | |
|
0
|
|
|
фрилансер
6440 / 5634 / 1127
Регистрация: 11.10.2019
Сообщений: 14,980
|
|
| 24.09.2023, 19:55 | |
|
0
|
|
|
Заблокирован
|
|||||||
| 24.09.2023, 19:59 | |||||||
|
Просто переполнение результата, вот и все.
первый элемент (1) Дианы похож на 6-ой элемент Никиты, первый элемент (1) Дианы похож на 7-ой элемент Никиты, ... шестой элемент (2) Дианы похож на 1-ый элемент Никиты, шестой элемент (2) Дианы похож на 2-ой элемент Никиты, ... Каждый с каждым
0
|
|||||||
|
фрилансер
6440 / 5634 / 1127
Регистрация: 11.10.2019
Сообщений: 14,980
|
|
| 24.09.2023, 20:04 | |
|
SmallEvil, хм, а я почему-то понял так, что нужно найти последовательность максимальной длины на обоих наборах
0
|
|
|
0 / 0 / 0
Регистрация: 24.09.2023
Сообщений: 3
|
|
| 24.09.2023, 20:11 [ТС] | |
|
0
|
|
|
Заблокирован
|
|
| 24.09.2023, 20:33 | |
|
0
|
|
| 24.09.2023, 20:33 | |
|
Помогаю со студенческими работами здесь
12
Написать приложение для поиска одинаковых значений пары ключ-значения в разных словарях
Выяснить, имеются ли пары соседствующих одинаковых символов и оставить только по одному из пары Нужно найти в массиве и распечатать пары одинаковых чисел
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|
Фото: Daniel Greenwood
kumehtar 13.11.2025
|
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга,
Ты же видел моря и метели.
Как сменялись короны и стяги,
Как эпохи стрелою летели.
- Этот мир — это крылья и горы,
Снег и пламя, любовь и тревоги,
И бескрайние. . .
|