Максимальное количество элементов массива B[], присутствующих в диапазонах [A[i] + K, A[i] – K]
Имея два массива A[] размера N и B[] размера M и целое число K , задача состоит в том, чтобы выбрать не более одного элемента из массива B[] для каждого элемента A[i] так, чтобы элемент лежал в диапазоне [A[i] – K, A[i] + K] (для 0 <= i <= N – 1 ) . Выведите максимальное количество элементов, которые можно выбрать из массива B[].
Примеры:
Input: N = 4, A[] = {60, 45, 80, 60}, M = 3, B[] = {30, 60, 75}, K= 5
Output: 2
Explanation :
B[0] (= 30): Not present in any of the ranges [A[i] + K, A[i] – K].
B[1] (= 60): B[1] lies in the range [A[0] – K, A[0] + K], i.e. [55, 65].
B[2] (= 75): B[2] lies in the range [A[2] – K, A[2] + K], i.e. [75, 85].Input: N = 3 A[] = {10, 20, 30}, M = 3, B[] = {5, 10, 15}, K = 10
Output: 2
Наивный подход: самый простой подход к решению проблемы — пройтись по массиву A[] , выполнить линейный поиск в массиве B[] и отметить посещенный, если выбрано значение массива B[] . Наконец, выведите максимальное количество элементов из массива B[] , которые можно выбрать.
Временная сложность: O(N * M)
Вспомогательное пространство: O(M)
Эффективный подход: отсортируйте оба массива A[] и B[] и попытайтесь присвоить элемент B[] , который находится в диапазоне [A[i] – K, A[i] + K]. Выполните следующие шаги, чтобы решить проблему:
- Отсортируйте массивы A[] и B[].
- Инициализируйте переменную, скажем, j как 0, чтобы отслеживать в массиве B[] и считать как 0 , чтобы сохранить ответ.
- Выполните итерацию в диапазоне [0, N – 1] и выполните следующие шаги:
- Повторяйте цикл while, пока j < M и B[j]< A[i] – K, затем увеличьте значение j на 1.
- Если значение j меньше M , а B[j] больше, чем равно A[i] – K , а B[j] меньше, чем равно A[i] + K , то увеличьте значение count и j на 1.
- После выполнения вышеуказанных шагов выведите значение count в качестве конечного значения ответа.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O (N * log (N))
Вспомогательное пространство: O(N)