给定一个数组，求每对整数的绝对差之和。
例如:给定 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))，然后遍历排序后的数组，如上所述将每个元素相乘。
关于algorithm - 求数组中每对整数的绝对差之和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5855066/