Найдите элемент массива, имеющий минимальную сумму абсолютных разностей со всеми остальными элементами массива.

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти минимальную сумму абсолютных разностей элемента массива со всеми элементами другого массива.

Input: arr[ ] = {1, 2, 3, 4, 5}, N = 5
Output: 3
Explanation: 
For arr[0](= 1): Sum = abs(2 – 1) + abs(3 – 1) + abs(4 – 1) + abs(5 – 1) = 10.
For arr[1](= 2): Sum = abs(2 – 1) + abs(3 – 2) + abs(4 – 2) + abs(5 – 2) = 7.
For arr[2](= 3): Sum = abs(3 – 1) + abs(3 – 2) + abs(4 – 3) + abs(5 – 3) = 6 (Minimum).
For arr[3](= 4): Sum = abs(4 – 1) + abs(4 – 2) + abs(4 – 3) + abs(5 – 4) = 7.
For arr[0](= 1): Sum = 10.

Input: arr[ ] = {1, 2, 3, 4}, N = 4
Output: 2

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

• Отсортируйте массив arr[] .
• В качестве требуемого ответа выведите средний элемент отсортированного массива.

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

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