Минимальное и максимальное количество элементов на расстоянии D от arr[i] в любом направлении

Для данного отсортированного массива arr[] и положительного целого числа D задача состоит в том, чтобы найти минимальное и максимальное количество элементов массива, лежащих на расстоянии D от элемента массива arr[i] в любом направлении, т. е. в диапазоне [обр[i] – D, обр[i]] или [обр[i], обр[i] + D] .

Примеры:

Input arr[] = {2, 4, 7, 11, 13, 14}, D = 4
Output: 1 3
Explanation:
The minimum number of array elements is included is 1 from arr[0](= 2) as the there exists only 1 element that lies over the range [-2, 2].
The minimum number of array elements is included is 3 from arr[3](= 11) as the there exists only 3 elements that lies over the range [11, 15].
Therefore, print 1, 3.

Input: arr[] = {1, 3, 5, 9, 14}, D = 5
Output: 1 3

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

• Инициализируйте две переменные, скажем, min и max , чтобы сохранить минимальный и максимальный элементы, включенные в диапазон расстояния D .
• Переберите массив arr[] и для каждого элемента выполните следующее:
  1. Инициализируйте переменную dist для вычисления количества точек, включенных в диапазон расстояния D .
  2. Выполните бинарный поиск слева от arr[i] и найдите элементы числового массива в диапазоне [arr[i] – D, arr[i]] , используя следующие шаги:
     • Инициализировать слева = 0, справа = i – 1 и на каждой итерации:
       • Найдите значение mid = (left + right) / 2 .
       • Если arr[mid] < arr[i] – D, то обновить значение left до mid + 1 . В противном случае обновите значение dist до mid и обновите значение right до mid-1 .
  3. Обновите значение min и max в соответствии со значением dist .
  4. Выполните бинарный поиск слева от arr[i] и найдите количество элементов массива в диапазоне [arr[i], arr[i] + D] , используя следующие шаги:
     • Инициализировать слева = i + 1, справа = N – i и на каждой итерации:
       • Найдите значение mid = (left + right) / 2 .
       • Если arr[mid] > arr[i] + D , то обновить значение справа до середины – 1 . В противном случае обновите значение dist до mid и обновите значение left до mid + 1 .
  5. Обновите значение min и max в соответствии со значением dist .
• После выполнения вышеуказанных шагов выведите значения min и max как результирующее минимальное и максимальное количество пройденных точек.

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

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