Среднее значение попарной разницы всех пар, образованных из заданных N целых чисел

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

Примеры:

Input: arr[] = {-1, 3, -5, 4}
Output: 5.166667
Explanation: There are 6 possible pair of points in the given array with the pairwise difference as: diff(-1, 3) = 4, diff(-1, -5) = 4, diff(-1, 4) = 5, diff(3, -5) = 8, diff(3, 4) = 1, diff(-5, 4) = 9. Therefore, average pairwise difference is (4 + 4 + 5 + 8 + 1 + 9)/6 = 31/6 = 5.166667.

Input: arr[] = { -1, 2, -3, 7, -6 }
Output: 6.2

Подход: Эту проблему можно решить, используя жадный подход и метод суммы префиксов. Если точки в массиве arr[] отсортированы, то сумма расстояний от i ^-й точки до всех больших точек может быть вычислена как: (arr[i+1] – arr[i]) + (arr[ i+2] – обр[i]) … + (обр[N-1] – обр[i]) => (обр[i+1] + обр[i+2]… + обр[N-1]) – обр[i] * (N – 1 – i) . Используя это наблюдение, данная проблема может быть решена с помощью следующих шагов:

• Сначала отсортируйте массив arr[] в порядке неубывания.
• Создайте массив суммы префиксов pre[] из массива arr[] .
• Перебрать каждый индекс i и добавить (pre[N – 1] – pre[i]) – arr[i] * (N – 1 – i) в переменную ans .
• Требуемый ответ: ans/количество пар => ans/(N*(N-1)/2) .

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

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