K-е наименьшее число в массиве, образованном произведением любых двух элементов из двух массивов

Даны два отсортированных массива A[] и B[] , состоящих из N и M целых чисел соответственно, задача состоит в том, чтобы найти K ^-е наименьшее число в массиве, образованном произведением всех возможных пар из массивов A[] и B[] соответственно. .

Примеры:

Input: A[] = {1, 2, 3}, B[] = {-1, 1}, K = 4
Output: 1
Explanation: The array formed by the product of any two numbers from array A[] and B[] respectively is prod[] = {-3, -2, -1, 1, 2, 3}. Hence, the 4th smallest integer in the prod[] array is 1.

Input: A[] = {-4, -2, 0, 3}, B[] = {1, 10}, K = 7
Output: 3

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

• Создайте функцию check(key) , которая возвращает, больше ли число элементов, меньших ключа в массиве продуктов, чем K , или нет. Это можно сделать с помощью метода двух указателей, аналогичного алгоритму, обсуждаемому в статье здесь.
• Выполните двоичный поиск в диапазоне [INT_MIN, INT_MAX], чтобы найти наименьшее число и такое, что количество элементов, меньших, чем ans , в массиве произведений не менее K .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

Ниже приведена реализация вышеуказанного подхода:

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