Учитывая два отсортированных массива и число x, найдите пару, сумма которой ближе всего к x, и у пары есть элемент из каждого массива .
Нам даны два массива ar1 [0… m-1] и ar2 [0..n-1] и число x, нам нужно найти пару ar1 [i] + ar2 [j] такую, что абсолютное значение (ar1 [i] + ar2 [j] — x) минимально.
Пример:
Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 32 Output: 1 and 30 Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 50 Output: 7 and 40
Мы настоятельно рекомендуем свернуть ваш браузер и попробовать это в первую очередь.
Простое решение — запустить два цикла. Внешний цикл рассматривает каждый элемент первого массива, а внутренний цикл проверяет пару во втором массиве. Мы отслеживаем минимальную разницу между ar1 [i] + ar2 [j] и x.
Мы можем сделать это за O (n) время, используя следующие шаги.
1) Объединить данные двух массивов во вспомогательный массив размером m + n, используя процесс слияния сортировки слиянием . При объединении сохраните другой логический массив размером m + n, чтобы указать, является ли текущий элемент в объединенном массиве аргументом ar1 [] или ar2 [].
2) Рассмотрим объединенный массив и используем алгоритм линейного времени, чтобы найти пару с суммой, ближайшей к x . Еще одна вещь, которую нам нужно рассмотреть только те пары, которые имеют один элемент из ar1 [] и другой из ar2 [], мы используем для этого логический массив.
Можем ли мы сделать это за один проход и O (1) лишний пробел?
Идея состоит в том, чтобы начать с левой стороны одного массива и правой стороны другого массива и использовать алгоритм, аналогичный шагу 2 вышеприведенного подхода. Ниже приводится подробный алгоритм.
1) Initialize a variable diff as infinite (Diff is used to store the difference between pair and x). We need to find the minimum diff. 2) Initialize two index variables l and r in the given sorted array. (a) Initialize first to the leftmost index in ar1: l = 0 (b) Initialize second the rightmost index in ar2: r = n-1 3) Loop while l = 0 (a) If abs(ar1[l] + ar2[r] - sum) < diff then update diff and result (b) If (ar1[l] + ar2[r] < sum ) then l++ (c) Else r-- 4) Print the result.
Ниже приводится реализация этого подхода.
|
Джава
|
python3
|
C #
|
PHP
|
Выход:
The closest pair is [7, 30]
Пара значений наименьшего различия между двумя несортированными массивами
Эта статья предоставлена Harsh. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Найти три ближайших элемента из заданных трех отсортированных массивов
- Учитывая отсортированный массив и число x, найдите пару в массиве, сумма которой ближе всего к x
- По сортированному и повернутому массиву найдите, есть ли пара с заданной суммой.
- Найти сумму пары из двух массивов с максимальной суммой
- Найти пару элементов, которые меняются суммой двух массивов
- Понимание списка Python, чтобы найти пару с заданной суммой из двух массивов
- Найти m-е наименьшее значение в k отсортированных массивах
- Генерация всех возможных отсортированных массивов из альтернативных элементов двух заданных отсортированных массивов
- Ближайшая пара продуктов в массиве
- Найти относительное дополнение двух отсортированных массивов
- Найти общие элементы в трех отсортированных массивах
- Объединить k отсортированных массивов | Набор 2 (разные размерные массивы)
- Пара с данным продуктом | Набор 1 (Найти, если какая-либо пара существует)
- Переставьте два массива так, чтобы сумма каждой пары была больше или равна K
- Найти подмассив с суммой, ближайшей к 0
0.00 (0%) 0 votes