查找数组中每对整数的绝对差值之和

Question

给定一个数组,找到每对整数的绝对差值之和.

例如:给定 a[]= {2,3, 5, 7 };

输出将是(3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.

它必须做得更好O(n^2).

原始数组不一定排序.

Answer 1

请注意,您将每个数字精确地添加k次(其中k是它的位置,如果您对列表进行排序)
也是,您将每个数字精确地减去n-1-k次,
您可以对列表进行排序(O(nlogn))然后迭代排序数组,如上所述乘以每个元素.

Answer 2

我想我找到了答案.我通过查看帖子中的结果表达式得到了它.

这是C++中的代码.

int AbsDiff(int a[], int n)
{
  if ( n < 2 ) return 0;
  sort(a,a+n);     
  int sum = 0;
  int i;
  for(i=n-1;i>=0;i--)
  {
    sum += (a[i]*(i) - a[i]*(n-i-1));
  }
  return sum;
}

Answer 3

例如:给定a [] = {2,3,5,7};
输出将是(3-2)+(5-2)+(7-2)+(5-3)+(7-3)+(7-5)= 17.

我想你可以

• 将每个数字的乘法与#count - 1相加,得到总数
• 将前面开头的每个数字的乘法与#count - 1相加,得到要减去的总数

这将成为 (7*3 + 5*2 +3*1) - (2*3 + 3*2 + 5*1) = 17