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

@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х

oldnewyear · 29.11.2016, 13:57

Предположу, что сначала нужно отсортировать второй массив - O(n log n), затем проходить по первому массиву - O(n), и искать бинарным поиском во втором массиве число x-array1[i], где x - заданное число - O(log n). Получаем временную сложность O(n log n) + O(n log n) = O(n log n)

echs · 29.11.2016, 15:05

А почему бы из массивов вообще не выкинуть числа
большие 7 (заменить на 0)?

@vkiper · 29.11.2016, 15:28 **[ТС]**

А почему бы из массивов вообще не выкинуть числа
большие 7 (заменить на 0)?

А если контрольное число будет скажем 30, а массивы будут выглядеть так:

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

ИМХО, нечего будет выкидывать из массивов... либо я не понял задумку.

Добавлено через 14 минут
По условиям задачи нет проблем с использованием доп. памяти,(извиняюсь, что не сказал сразу) т.е. разрешается создавать временные массивы и т.д. Я вначале думал создать два новых массива, в которые занес бы разницу между контрольным числом и каждым значением, т.е.

C++
1
2
array1_1[i] = checkNum - array1[i]
array2_1[i] = checkNum - array2[i]

Потом мне показалось, что ничего это не даст... не знаю.

@Shamil1 · 29.11.2016, 15:42

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

и выявить ближайший случай

какой случай считается ближайшим?

@vkiper · 29.11.2016, 16:33 **[ТС]**

какой случай считается ближайшим?

Мне не дали четкое определение. Пусть это будет "наименьший индекс" первого массива, скажем, в самом первом примере это индекс 0, т.е. array1[0]
Либо пускай это будет единственное совпадение, тогда задача облегчается, т.е. такой случай у нас только один.

@Shamil1 · 29.11.2016, 17:15

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

без вложенных циклов

А что означает "без вложенных циклов"? Например, вот такой вариант:

C#
1
var res = array1.SelectMany(x => array2.Select(y => x + y)).FirstOrDefault(x => x != n);

вложенных циклов не видно.

@vkiper · 29.11.2016, 18:20 **[ТС]**

А что означает "без вложенных циклов"?

Есть такое понятие - "цикл в цикле". Пример - "пузырьковая сортировка". То, что вы показали, ИМХО, также "цикл в цикле", внутренняя реализация. Я не силен в Шарпе и могу ошибаться, но мне кажется, что это так.

@Excalibur921 · 29.11.2016, 23:19

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

попросили найти более простое решение

Простое значит без спец алгоритмов и очевидное для не программиста. Как бы решал любой человек.

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

Стандартное решение подразумевает цикл в цикле,

Вот это и есть простое решение.

@vkiper · 29.11.2016, 23:51 **[ТС]**

Возможно, я не точно выразился насчет "простого" решения. Подразумевалось уйти от сложности N*N к меньшей сложности. Намекнули, что есть какой-то фокус. И... вообще-то, меня спрашивали как программиста

Не хочу вгонять никого в конфуз, если мне удастся добраться до этих людей, я раскручу их на ответ и выложу его здесь.

oldnewyear · 30.11.2016, 01:13

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

Возможно, я не точно выразился насчет "простого" решения. Подразумевалось уйти от сложности N*N к меньшей сложности. Намекнули, что есть какой-то фокус. И... вообще-то, меня спрашивали как программиста

Не хочу вгонять никого в конфуз, если мне удастся добраться до этих людей, я раскручу их на ответ и выложу его здесь.

А чем вам мой алгоритм не понравился?

@Excalibur921 · 30.11.2016, 01:20

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

уйти от сложности N*N

Нереально на случайных данных.

1)Может у данных есть закономерность? Построить их как 2 графика функции. X индекс, Y значение. Может второй массив это сдвиг или растяжение первого.
По другому нереально…
Или как то разложить форму функции первого массива на элементарные сигналы например синусоиды.
Может второй и первый массив это одна и та же формула псевдослучайная последовательность только разные фазы( начальное число генератора).

Если нет закона в данных то и нет способа не перебирать все.
Можно размазывать суть N*N на подготовку данных.

oldnewyear · 30.11.2016, 02:43

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

Нереально на случайных данных

Алгоритм в первом ответе

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

Code
1
2
3
4
5
6
1. MergeSort(Array2)
2. foreach i in Array1 {
     c = BinarySearch(Array2,x-i)
     if c!= null { break}
}
3. Print 'i+c=x'

сложность O(n log n)

@vkiper · 30.11.2016, 10:33 **[ТС]**

сложность O(n log n)

ИМХО, сортировка массива предусматривает вложенные циклы. Опять же, я не считаю себя крутым экспертом, поэтому не буду настаивать с пеной у рта. У меня теперь цель - добраться до того студента, который меня всем этим загрузил, и раскрутить его на ответ.

@Shamil1 · 30.11.2016, 10:55

Можно вообще без циклов обойтись, если использовать рекурсию.

oldnewyear · 30.11.2016, 11:20

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

ИМХО, сортировка массива предусматривает вложенные циклы. Опять же, я не считаю себя крутым экспертом, поэтому не буду настаивать с пеной у рта. У меня теперь цель - добраться до того студента, который меня всем этим загрузил, и раскрутить его на ответ.

MergeSort это один из рекурсивных divide and conquer алгоритмов сортировки. Временная сложность O(n log n)

@Excalibur921 · 30.11.2016, 12:29

Если ответ начальный элемент первого массива и любой индекс второго то самый быстрый N*N, иначе сортировка очевидно сильно ускорит поиск.

Т.е. пока алгоритм поста 2 будет только сортировать массив алгоритм N*N уже даст ответ чисто по тактам процессора выиграет. Хотя в теории он медленней =).

Если ответ будет в конце первого массива то N*N проиграет как любой брутофорс.

Если в данных выявить закономерность то никакая сортировка массива не выиграет формуле в 1 строчку но это уже нечестно.

oldnewyear · 30.11.2016, 12:38

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

Если ответ начальный элемент первого массива и любой индекс второго то самый быстрый N*N, иначе сортировка очевидно сильно ускорит поиск.

Т.е. пока алгоритм поста 2 будет только сортировать массив алгоритм N*N уже даст ответ чисто по тактам процессора выиграет. Хотя в теории он медленней =).

В анализе алгоритмов обычно оценивается хучший вариант. Теоретически, n log n значительно быстрее n^2. На практике, иногда алгоритм с большей временной сложностью работает быстрее, все зависит от конкретных входных данных

echs · 30.11.2016, 14:37

vkiper
А если элементы второго массива уменьшить на 8.
Тогда вам положительные элементы вообще можно
игнорировать. А сумма вам потребуется равная 0.

@vkiper · 01.12.2016, 13:41 **[ТС]**

vkiper
А если элементы второго массива уменьшить на 8.
Тогда вам положительные элементы вообще можно
игнорировать. А сумма вам потребуется равная 0.

Я думал про этот вариант. Но не нашел, как при этом можно избежать N*N

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

oldnewyear 440 / 432 / 159 Регистрация: 21.05.2016 Сообщений: 1,338
	29.11.2016, 13:57
	Предположу, что сначала нужно отсортировать второй массив - O(n log n), затем проходить по первому массиву - O(n), и искать бинарным поиском во втором массиве число x-array1[i], где x - заданное число - O(log n). Получаем временную сложность O(n log n) + O(n log n) = O(n log n) 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	29.11.2016, 15:05
	А почему бы из массивов вообще не выкинуть числа большие 7 (заменить на 0)? 0

@vkiper 17 / 17 / 6 Регистрация: 11.11.2015 Сообщений: 146
	29.11.2016, 23:51 [ТС]
	Возможно, я не точно выразился насчет "простого" решения. Подразумевалось уйти от сложности N*N к меньшей сложности. Намекнули, что есть какой-то фокус. И... вообще-то, меня спрашивали как программиста Не хочу вгонять никого в конфуз, если мне удастся добраться до этих людей, я раскручу их на ответ и выложу его здесь. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	30.11.2016, 10:55
	Можно вообще без циклов обойтись, если использовать рекурсию. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	30.11.2016, 12:29
	Если ответ начальный элемент первого массива и любой индекс второго то самый быстрый NN, иначе сортировка очевидно сильно ускорит поиск. Т.е. пока алгоритм поста 2 будет только сортировать массив алгоритм NN уже даст ответ чисто по тактам процессора выиграет. Хотя в теории он медленней =). Если ответ будет в конце первого массива то N*N проиграет как любой брутофорс. Если в данных выявить закономерность то никакая сортировка массива не выиграет формуле в 1 строчку но это уже нечестно. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	30.11.2016, 14:37
	vkiper А если элементы второго массива уменьшить на 8. Тогда вам положительные элементы вообще можно игнорировать. А сумма вам потребуется равная 0. 0