查找数组中每对整数的绝对差值之和-Java 学习之路

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

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

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

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

原始数组不一定要排序 .

7 回答

我想我发布这篇文章的时间已经很晚了，但我想这个CPP计划应该可行 .

//JUST LIKE ANIMALS !!!!

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll funcy(ll a[], ll n)
{

ll sum = 0;
ll i;
for(i=0;i<n;i++)
{
sum += (a[i]*(i) - a[i]*(n-i-1));
}
return sum;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll i,n;cin>>n;ll v[n+1];
for(i=0;i<n;i++)cin>>v[i];
sort(&v[0],&v[n]);
cout<<AbsDiff(v,n);
return 0;

}

附：提供n> 2 . 如果这里有问题，请随时纠正我 .

回复于 2024-04-28T07:40:54+08:00

0
如果数组的大小= 4，下面的代码计算[0]（ - 3）a [1]（ - 1）a [2]（1）a [3]（3） .
```
result := 0
for i := 0 to sizeof(a)-1 do
begin
   result := result + a[i] * (i*2 - sizeof(a) + 1)
end
```
如果需要处理排序数组，可以先使用O（n * log（n））复杂度的快速排序算法对其进行排序 .
回复于 2024-04-28T07:40:54+08:00
0
例如：给定[] = {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
回复于 2024-04-28T07:40:54+08:00
8
只是另一种观点 . 这是Mathematica代码：
```
With[{n = Length@# - 1}, Range[-n, n, 2].Sort[#]] &
```
n =比列表长度少一个

Range[-n, n, 2] 创建一个包含 -n 到 n 的数字的列表，步长为 2 ，例如 Range[-4, 4, 2] = {-4, -2, 0, 2, 4}

. 是矢量点积，例如 {a, b, c} . {x, y, z} = a x + b y + c z

Sort 只是排序 .

所以，对于你的例子，我们有： {-3, -1, 1, 3} . {2, 3, 5, 7} = 17

这是列表长度与时间的关系图：
回复于 2024-04-28T07:40:54+08:00
27

请注意，您将每个数字恰好添加k次（如果您对列表进行排序，则k为其位置）
另外，你每个数字减去n-1-k次
您可以对列表进行排序（O（nlogn）），然后迭代排序的数组，将每个元素相乘，如上所述 .

回复于 2024-04-28T07:40:54+08:00

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

这是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;
}

回复于 2024-04-28T07:40:54+08:00

看看 JAVA 中的这一小段工作代码 . 希望它有所帮助并且有意义 .

import java.util.Arrays;

public class PairDifference {

    public static void main(String[] args) {
        int[] arr = {2,3,5,7};
        System.out.println(getPairDifference(arr));
    }

    static int getPairDifference(int[] a){
        int diff = 0;
        Arrays.sort(a);
        int n = a.length;
        for(int i=0; i<n; i++)
            diff += (a[i]*i) - (a[n-1-i]*i);

        return diff;
    }

}

回复于 2024-04-28T07:40:54+08:00

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

7 回答

相关问题