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

@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 вообще не сравниваются. Точнее, они могут сравниваться при некоторых условиях, но вероятность этого мала.

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
Генератор паролей (вариант №2) Maks 30.10.2026 Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .	Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .	Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .	Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .

@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