Максимизируйте произведение двух ближайших чисел другого массива для каждого элемента в данном массиве

Опубликовано: 20 Сентября, 2022

Учитывая массивы arr1[] размера M и arr2[] размера N , имеющие длину не менее 2, задача состоит в том, чтобы для каждого элемента в arr1[] максимизировать произведение двух элементов в arr2[] , которые являются ближайшими к элементу в arr1 []. Ближайшие элементы должны присутствовать по разным индексам.

Пример:

Input: arr1 = [5, 10, 17, 22, -1], arr2 = [-1, 26, 5, 20, 14, 17, -7]
Output: -5 70 340 520 7
Explanation: 
The closest elements to 5 are 5 and -1, therefore the maximum product is -5
The closest elements to 10 are 5 and 14, therefore the maximum product is 70
The closest elements to 17 are 20, 17, and 14, therefore the maximum product of 20 and 17 is 340
The closest elements to 22 are 20 and 26, therefore the maximum product is 520
The closest elements to -1 are -1, 5, and -7, therefore the maximum product of -1 and -7 is 7

Input: arr1 = [3, 9, 4, -1, 22], arr2 = [-1, 1, 21, 8, -3, 20, 25]
Output: -1 8 8 3 420

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, чтобы отсортировать массив arr2 в порядке возрастания, затем для каждого элемента в arr1 найти ближайший к нему элемент в arr2, используя бинарный поиск. Для решения проблемы можно выполнить следующие шаги:

  • Отсортировать массив arr2 по возрастанию
  • Итерируйте массив arr1 и на каждой итерации применяйте бинарный поиск к arr2 , чтобы найти индекс элемента, ближайший к arr1[i], скажем, x :
    • Если предыдущего индекса x-1 не существует, вернуть arr2[x] * arr2[x+1]
    • Иначе Если следующего индекса x+1 не существует, вернуть arr2[x] * arr2[x-1]
    • В противном случае проверьте, какой элемент между arr2[x-1] и arr2[x+1] ближе к arr1[i]:
      • Если arr2[x-1] ближе, верните arr2[x] * arr2[x-1]
      • В противном случае, если arr2[x+1] ближе, верните arr2[x] * arr2[x+1]
      • В противном случае, если оба arr2[x-1] и arr2[x+1] равноудалены от arr1[i] , верните максимальное произведение между arr2[x] * arr2[x+1] и arr2[x] * arr2[x+ 1]

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(N * log N + M * log N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ