Сравнение двух массивов без вложенных циклов

@vkiper · Регистрация: 11.11.2015

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

Извиняюсь, что помещаю здесь этот вопрос, я сам по идее должен был догадаться, но никак не могу. Второй день гружусь, без толку

Имеются два массива с числами(int), одного размера, скажем, в каждом массиве по 20 чисел, больше нуля. Например:

C++
1
2
array1[20] = { 2, 5, 3, 7, 9, 6, ....}
array2[20] = { 8, 4, 1, 6, 13, 21, ....}

Дано контрольное число 8. Нужно сопоставить два массива и выявить ближайший случай, когда число из первого и число из второго массива дадут в сумме эту восьмерку.
В данном случае это будет: array1[0] + array2[3] = 8 // 2 + 6 = 8
Стандартное решение подразумевает цикл в цикле, т.е. сложность алгоритма будет N*N, если за N мы берем размер массива.
Меня попросили найти более простое решение, без вложенных циклов. Догадываюсь, что где-то в сети или в учебниках оно разжевано, но не могу найти.
Всем 10х

@vrm2 · 15.02.2022, 23:05

Кладем значения одного массива в hashmap (dict).
Пробегаемся по второму массиву и проверяем наличие числа в первом (number in dict).

Никаких вложенных циклов. Сложность O(N).
Или я неправильно понял задачу?

@vantfiles · 15.02.2022, 23:37

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

Кладем значения одного массива в hashmap (dict).

n log n

@vrm2 · 15.02.2022, 23:50

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

n log n

O(N), т.к. операция put занимает O(1).
https://en.wikipedia.org/wiki/Hash_table

@vantfiles · 16.02.2022, 00:02

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

Пробегаемся по второму массиву и проверяем наличие числа в первом

n^2
по сортированному
n log n

@vrm2 · 16.02.2022, 00:12

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

n^2
по сортированному
n log n

Пробегам по второму массиву - N элементов.
Для каждого ищем этот элемент во первом массиве за O(1).
Итого O(N)

Сортировать не нужно

@vantfiles · 16.02.2022, 00:19

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

Для каждого ищем этот элемент во первом массиве за O(1).

????????

@vrm2 · 16.02.2022, 00:25

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

????????

???????

Потрудитесь выражаться яснее

@vantfiles · 16.02.2022, 00:30

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

ищем этот элемент

то есть перебираем весь второй массив.

Добавлено через 43 секунды

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

за O(1).

да просто праздник какой-то

@vrm2 · 16.02.2022, 00:48

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

да просто праздник какой-то

Что удивительного? Ознакомьтесь со структурой hash map. Операция вставки и поиска в ней осуществляется за O(1).

Объясню еще раз, на всякий случай. Я решаю задачу поиска одинаковых значений в двух массива. Т.е. значений, которые есть и в одном, и в другом. Сравнение двух массивов без вложенных циклов

1. Складываем значения из первого массива в hash map. Это занимает время O(N).
2. Затем бежим по второму массиву и смотрим, есть ли это значение в hash map (это действие занимает O(1)).
Если в hash map этот элемент есть, то мы нашли "одинаковый" элемент, содержащийся в двух массивах. Этот пункт тоже O(N)

Итого: O(N), без вложенных циклов

@vantfiles · 16.02.2022, 01:12

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

Затем бежим по второму массиву и смотрим, есть ли это значение в hash map

за O(1) ? то есть от размера массива ничего не зависит?

Добавлено через 11 минут

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

Операция вставки и поиска в ней осуществляется за O(1).

Это так, но Вы абсолютно не понимаете, что это значит.

@vrm2 · 16.02.2022, 09:35

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

за O(1) ? то есть от размера массива ничего не зависит?

Да.

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

Это так, но Вы абсолютно не понимаете, что это значит

Я прекрасно понимаю, что такое O(1), O(N) и прочее Big-O

P.S. Ваши посты не конструктивны. Вы не пытаетесь обсудить задачу и ее решение.
По существу есть замечания? Если видите ошибки, укажите на них (в контексте задачи).

@vantfiles · 16.02.2022, 10:37

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

По существу есть замечания?

Да, есть. Покажите код на любом языке - будет что обсудить.

@vrm2 · 16.02.2022, 10:51

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

Да, есть. Покажите код на любом языке - будет что обсудить

Python
1
2
3
4
5
def solve(arr1, arr2):
  s = set(arr1)
  for x in arr2:
    if x in s:
      print('Присутствует в обоих массивах', x)

@vantfiles · 16.02.2022, 10:59

я так и знал
зачем на второй итерации вы снова сравниваете элементы 2-1, если на первой уже были 1-2?

@vrm2 · 16.02.2022, 11:10

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

зачем на второй итерации вы снова сравниваете элементы 2-1, если на первой уже были 1-2?

Что такое 2-1 и 1-2?

Добавлено через 1 минуту
Вообще, это задача пересечения двух множеств.
set(arr1) & set(arr2)

Ее сложность O(N)

@vantfiles · 16.02.2022, 11:14

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

Ее сложность O(N)

у Вас n^2 в коде.

@vrm2 · 16.02.2022, 11:16

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

у Вас n^2 в коде.

У меня нет слов.... Попытайтесь доказать. Укажу Вам на ошибку.

@vantfiles · 16.02.2022, 11:20

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

for x in arr2:
if x in s:

итого n^2

@vrm2 · 16.02.2022, 13:24

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

итого n^2

Не очень похоже на доказательство.

P.S. Учтите, что s - множество (set)

@Shamil1 · 17.02.2022, 02:08

Доступ к сету О(1). То есть, затраты времени линейно зависят от размера.
Более того, поиск в каком-нибудь 32-битном дереве на множестве инт32 тоже линейно зависит от размера. Его можно записать без циклов (через вложенные ифы).

Добавлено через 3 минуты

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

зачем на второй итерации вы снова сравниваете элементы 2-1, если на первой уже были 1-2?

В приведённом коде 1 и 2 вообще не сравниваются. Точнее, они могут сравниваться при некоторых условиях, но вероятность этого мала.

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .	Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .
Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .

@vrm2 431 / 302 / 90 Регистрация: 03.12.2015 Сообщений: 741
	15.02.2022, 23:05
	Кладем значения одного массива в hashmap (dict). Пробегаемся по второму массиву и проверяем наличие числа в первом (number in dict). Никаких вложенных циклов. Сложность O(N). Или я неправильно понял задачу? 0

@vantfiles 1018 / 1921 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	16.02.2022, 10:59
	я так и знал зачем на второй итерации вы снова сравниваете элементы 2-1, если на первой уже были 1-2? 0