发现每对整数的绝对差和从一个数组 [英] Finding sum of Absolute Difference of Every pair of integer from an array

问题描述

给定的阵列，发现每一个整数对的绝对差的总和。

Given an array, find the sum of the absolute difference of every pair of integers.

例如：由于 A [] = {2,3，5，7};

输出将（3-2）+（5-2）+（7-2）+（5-3）+（7-3）+（7-5）= 17 。

必须比为O（n ^ 2）。

原始阵列不一定排序

推荐答案

请注意您添加的每个数字恰好k次（其中k为它的地方，如果你对列表排序）
也，则恰好减去每个数n-1-k次
可以对列表进行排序（O（nlogn）），然后遍历排序后的数组，上述每个元素相乘。

note you add each number exactly k times (where k is its place if you sort the list)
also, you subtract each number exactly n-1-k times
you can sort the list (O(nlogn)) and then iterate over the sorted array, multiplying each element as mentioned above.

这篇关于发现每对整数的绝对差和从一个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！