K-й наибольший попарный продукт, возможный из данных двух массивов

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

Даны два массива arr[] и brr[] , содержащие целые числа. Задача состоит в том, чтобы найти K -е наибольшее произведение пары (arr[i], brr[j]) .

Примеры:

Input: arr[] = {1, -2, 3}, brr[] = {3, -4, 0}, K = 3
Output: 3
Explanation: All product combinations in descending order are : [9, 8, 3, 0, 0, 0, -4, -6, -12] and 3rd largest element is 3.

Input: arr[] = {-1, -5, -3}, brr[] = {-3, -4, 0}, K =5
Output: 4
Explanation: All product combinations in descending order are : [20, 15, 12, 9, 4, 3, 0, 0, 0] and 5th largest element is 4.

Наивный подход: сгенерируйте все возможные комбинации продуктов для каждого элемента массива arr[] с каждым элементом массива brr[] . Затем отсортируйте массив результатов и верните K-й элемент массива результатов.

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

Эффективный подход: эту проблему можно решить с помощью жадного подхода и кучи. Выполните следующие шаги, чтобы решить данную проблему.

  • Отсортируйте массив brr[] .
  • Сохраняйте массив большего размера в массиве arr[] .
  • Создайте максимальную кучу для хранения элементов с соответствующими индексами.
  • Пройдите каждый элемент из массива arr[] . Элемент может быть как положительным, так и отрицательным.
  • Положительный : умножить текущий элемент из arr[] на самый большой элемент отсортированного массива brr[] . Чтобы обеспечить получение максимального элемента.
  • Отрицательный : в этом случае умножается на наименьшее значение , т.е. на первый элемент массива brr[] . Это связано со свойством отрицания, так как большее значение можно получить путем умножения на наименьшее.
  • Вставьте три значения в кучу так, чтобы: ( product, i, j ) где i & j - индексы массивов arr[] и brr[] .
  • Теперь запустите цикл for K раз и извлеките элементы из кучи.
  • Теперь проверьте, является ли значение, присутствующее в arr[i] , положительным или отрицательным.
  • Положительный : Итак , next_j = (current_j – 1) , потому что, поскольку использовалась максимальная куча, все более высокие индексы, возможно, уже были извлечены из кучи.
  • Отрицательный : next_j = (current_j +1) , потому что все меньшие значения, дающие более крупные элементы, возможно, уже были извлечены из кучи.
  • Наконец, верните ответ

Примечание. Максимальная куча реализована с помощью минимальной кучи путем инвертирования знаков значений при их вставке в кучу в Python.

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

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

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