Минимальное абсолютное значение (K – arr[i]) для всех возможных значений K в диапазоне [0, N – 1]

Для данного положительного целого числа N и отсортированного массива arr[] , состоящего из M целых чисел, задача состоит в том, чтобы найти минимальное абсолютное значение (K – arr[i]) для всех возможных значений K в диапазоне [0, N – 1 ] .

Примеры:

Input: N = 5, arr[] = {0, 4}
Output: 0 1 2 1 0
Explanation:
Below are the possible minimum value for all possible values of K over the range [0, N – 1]:

• K = 0: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 0. Therefore, the value is abs(0 – 0) = 0.
• K = 1: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 0. Therefore, the value is abs(1 – 0) = 1.
• K = 2: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 0. Therefore, the value is abs(2 – 0) = 2.
• K = 3: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 4. Therefore, the value is abs(3 – 4) = 1.
• K = 4: The minimum value of abs(K – arr[i]) is obtained by considering arr[i] as 4. Therefore, the value is abs(4 – 4) = 0.

Input: N = 6, arr[] = {0, 1, 4, 5}
Output: 0 0 1 1 0 0

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

• Инициализируйте переменную, скажем, ind как 0 , и переменную, скажем, prev как arr[0] , которая хранит ранее присвоенное значение.
• Переберите диапазон [0, N – 1], используя переменную K , и выполните следующие шаги:
  • Инициализируйте переменную, скажем, расстояние , чтобы сохранить минимальное абсолютное значение (K – arr[i]) .
  • Если значение i меньше, чем arr[0] , то обновить значение расстояния до (arr[0] – i) .
  • В противном случае, если значение i не меньше prev , значение (ind + 1) меньше M и значение i не больше arr[ind + 1] , выполните следующие шаги:
    • Обновите значение расстояния до минимума (i – prev) и (arr[ind + 1] – i) .
    • Если значение i равно arr[ind + 1] , тогда обновите значение Distance до 0 , prev до arr[ind + 1] и увеличьте значение ind на 1 .
  • Если значение i больше, чем prev , то обновить значение расстояния до (i – prev) .
  • После выполнения вышеуказанных шагов выведите значение расстояния как минимальное абсолютное значение (K – arr[i]) для текущего значения K .

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

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