blocks|key|2407389|text|注意，每个数字恰好相加k次(如果对列表进行排序，其中k是它的位置)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2407390|同样，你将每个数字精确地减去n-1-k次|2407391|您可以对列表进行排序(O(nlogn))，然后迭代排序后的数组，如上所述将每个元素相乘。|2407392|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

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.

blocks|key|4197037|text|我想我已经找到答案了。我通过查看我的帖子中的结果表达式得到了它。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4197038|以下是C%2B%2B中的代码。|4197039|++++int+AbsDiff(int+a[],+int+n)
++++{
++++++if+(+n+<+2+)+return+0;
++++++sort(a,a%2Bn);+++++
++++++int+sum+=+0;
++++++int+i;
++++++for(i=n-1;i>=0;i--)
++++++{
++++++++sum+%2B=+(a[i]*(i)+-+a[i]*(n-i-1));
++++++}
++++++return+sum;
++++}|code-block|syntax|javascript|4197040|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I think I have found the answer. I got it by looking into the result expression in my post.
Here is the code in C++.
<pre class="lang-cpp prettyprint-override"><code> int AbsDiff(int a[], int n)
 {
 if ( n &lt; 2 ) return 0;
 sort(a,a+n); 
 int sum = 0;
 int i;
 for(i=n-1;i&gt;=0;i--)
 {
 sum += (a[i]*(i) - a[i]*(n-i-1));
 }
 return sum;
 }
</code></pre>

blocks|key|2123193|text|以|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2123194|为例:给定a[]=+{2,3，5，7+}；|blockquote|2123195|2123196|输出将是(3-2)+%2B+(5-2)+%2B+(7-2)+%2B+(5-3)+%2B+(7-3)+%2B+(7-5)+=+17。|2123197|2123198|我想你可以|2123199|计数求和从#|2123200|-1开始的每个数字的乘法得到总计数求和从前面开始的每个数字与#|unordered-list-item|2123201|-1的乘积得到要减去的总数|2123202|这样就变成了(7*3+%2B+5*2+%2B3*1)+-+(2*3+%2B+3*2+%2B+5*1)+=+17|offset|length|style|CODE|2123203|entityMap^0|0|0|0|0|0|0|0|0|0|6|15|0^^$0|@$1|2|3|4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|10|8|@]|9|@]|A|$]]|$1|E|3|-4|5|6|7|11|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|12|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|13|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|14|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|15|8|@]|9|@]|A|$]]|$1|M|3|N|5|O|7|16|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|17|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|18|8|@$T|19|U|1A|V|W]]|9|@]|A|$]]|$1|X|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|Y|$]]

<blockquote>
 For example: Given a[]= {2,3, 5, 7 }; 
 output would be (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.
</blockquote>

I suppose you could 

<ul>
<li>Sum the multiplication of each number starting backwards with #count - 1 to get the total </li>
<li>Sum the multiplication of each number starting up front with #count - 1 to get the total to subtract</li>
</ul>

This would then become <code>(7*3 + 5*2 +3*1) - (2*3 + 3*2 + 5*1) = 17</code>

blocks|key|4197240|text|首先，需要在O(nlogn)时间内对数组进行排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4197241|现在我不会给你这个问题的确切解决方案，而是给你一个解决这个问题的直觉。如果我们尝试推广索引i处的特定数字被添加的次数和它被减去的次数，那么对于每个索引i，我们可以使用数学推导的公式来计算每个数字在O(N)时间和O(1)额外空间的绝对差中的贡献总和。|offset|length|style|BOLD|4197242|如果您在理解此概念时遇到困难，可以参考此视频。|4197243|视频链接：-+https://youtu.be/A4sz4kNDa-8|4197244|entityMap|0|LINK|mutability|MUTABLE|url|https://youtu.be/A4sz4kNDa-8^0|0|2Q|Q|0|0|7|S|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@$D|V|E|W|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|Y|8|@]|9|@$D|Z|E|10|1|11]]|A|$]]|$1|L|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|S]]]]

First of all array needs to be sorted in O(nlogn) time.

Now I would not give you the exact solution to this problem rather I would give you an intuition to solve this problem. 
If we try to generalize count of the number of times a particular number at index i is getting added and number of times it is being subtracted then for every index i we can use that mathematically derived formula to compute the sum of contributions of every number in the absolute difference in O(N) time and O(1) extra space.

You can refer to this video if you find difficulties in understanding this concept.

Video Link:- <a href="https://youtu.be/A4sz4kNDa-8" rel="nofollow noreferrer">https://youtu.be/A4sz4kNDa-8</a>

blocks|key|2407452|text|这只是一个不同的观点。以下是Mathematica的代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2407453|With[{n+=+Length@#+-+1},+Range[-n,+n,+2].Sort[#]]+&+|code-block|syntax|javascript|2407454|n+=比列表长度小1|offset|length|style|CODE|2407455|Range[-n,+n,+2]创建一个列表，其中包含从-n到n的数字，以2为步长，例如Range[-4,+4,+2]+=+{-4,+-2,+0,+2,+4}|2407456|.是向量点积，例如{a,+b,+c}+.+{x,+y,+z}+=+a+x+%2B+b+y+%2B+c+z|2407457|Sort只是排序。|2407458|因此，对于您的示例，我们使用：{-3,+-1,+1,+3}+.+{2,+3,+5,+7}+=+17|2407459|以下是列表长度与时间的关系图：|2407460|​|2407461|📷|atomic|2407462|2407463|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/356462ee171e3f0b4df11fe272b3510f.gif|imageAlt^0|0|0|0|1|0|0|F|R|2|U|1|10|1|17|F|1P|H|0|0|1|9|L|X|F|0|0|4|0|F|T|1B|2|0|0|0|0|1|0|0|0^^$0|@$1|2|3|4|5|6|7|1B|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1C|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1D|8|@$I|1E|J|1F|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|1G|8|@$I|1H|J|1I|K|L]|$I|1J|J|1K|K|L]|$I|1L|J|1M|K|L]|$I|1N|J|1O|K|L]|$I|1P|J|1Q|K|L]|$I|1R|J|1S|K|L]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1T|8|@$I|1U|J|1V|K|L]|$I|1W|J|1X|K|L]|$I|1Y|J|1Z|K|L]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|20|8|@$I|21|J|22|K|L]]|9|@]|A|$]]|$1|S|3|T|5|6|7|23|8|@$I|24|J|25|K|L]|$I|26|J|27|K|L]]|9|@]|A|$]]|$1|U|3|V|5|6|7|28|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|29|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|10|7|2A|8|@]|9|@$I|2B|J|2C|1|2D]]|A|$]]|$1|11|3|X|5|6|7|2E|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|2F|8|@]|9|@]|A|$]]]|13|$14|$5|15|16|17|A|$18|19|1A|-4]]]]

Just an alternative perspective on this. Here is Mathematica code:

<pre><code>With[{n = Length@# - 1}, Range[-n, n, 2].Sort[#]] &amp; 
</code></pre>

<code>n</code> = one less than the length of the list

<code>Range[-n, n, 2]</code> creates a list with numbers from <code>-n</code> to <code>n</code> in steps of <code>2</code>, e.g. <code>Range[-4, 4, 2]</code> = <code>{-4, -2, 0, 2, 4}</code>

<code>.</code> is vector dot product, e.g. <code>{a, b, c} . {x, y, z}</code> = <code>a x + b y + c z</code>

<code>Sort</code> is just sort.

So, for your example, we have: <code>{-3, -1, 1, 3} . {2, 3, 5, 7}</code> = <code>17</code>

Here is a plot of list length versus time:

<img src="https://i.stack.imgur.com/jKLDo.gif" alt="enter image description here">

blocks|key|2123312|text|如果数组大小=+4，下面的代码计算a(-3)+%2B+a1(-1)+%2B+a2(1)+%2B+a3(3)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2123313|result+:=+0
for+i+:=+0+to+sizeof(a)-1+do
begin
+++result+:=+result+%2B+a[i]+*+(i*2+-+sizeof(a)+%2B+1)
end|code-block|syntax|javascript|2123314|如果需要处理排序数组，可以先用O(n*log(n))复杂度的快速排序算法进行排序。|2123315|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The code below calculates a[0](-3) + a[1](-1) + a[2](1) + a[3](3), if size of array = 4.

<pre><code>result := 0
for i := 0 to sizeof(a)-1 do
begin
 result := result + a[i] * (i*2 - sizeof(a) + 1)
end
</code></pre>

If you need to deal with sorted array, you can sort it at first by quick sort algorithm with O(n*log(n)) complexity.

blocks|key|4197176|text|我想我有点晚了，但我想这个CPP程序应该可以工作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4197177|//JUST+LIKE+ANIMALS+!!!!

#include<bits/stdc%2B%2B.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%2B%2B)
{
sum+%2B=+(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%2B1];
for(i=0;i<n;i%2B%2B)cin>>v[i];
sort(&v[0],&v[n]);
cout<<AbsDiff(v,n);
return+0;|code-block|syntax|javascript|4197178|}|4197179|附注：提供n>2，如果这里有什么问题，请随时纠正我。|4197180|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

I think I am little late to post this but I guess this CPP program should work.

<pre><code>//JUST LIKE ANIMALS !!!!

#include&lt;bits/stdc++.h&gt;
using namespace std;
typedef long long int ll;

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

ll sum = 0;
ll i;
for(i=0;i&lt;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&gt;&gt;n;ll v[n+1];
for(i=0;i&lt;n;i++)cin&gt;&gt;v[i];
sort(&amp;v[0],&amp;v[n]);
cout&lt;&lt;AbsDiff(v,n);
return 0;
</code></pre>

} 

P.s. Provided n>2. Please if there is something wrong in this , feel free to correct me.

blocks|key|504018|text|看一下JAVA中的这小段工作代码。希望它能帮上忙，也能说得通。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|504019|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%2B%2B)
++++++++++++diff+%2B=+(a[i]*i)+-+(a[n-1-i]*i);

++++++++return+diff;
++++}

}|code-block|syntax|javascript|504020|entityMap^0|3|4|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|P|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|L|$]]

Have a look at this small piece of working code in JAVA.
Hope it helps and make sense.

<pre><code>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&lt;n; i++)
 diff += (a[i]*i) - (a[n-1-i]*i);

 return diff;
 }

}
</code></pre>

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

For example: Given <code>a[]= {2,3, 5, 7 };</code>

output would be <code>(3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17</code>.

It must be done better than <code>O(n^2)</code>.

The original array isn't necessarily sorted.

Finding sum of Absolute Difference of Every pair of integer from an array

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

给定一个数组，求出每对整数的绝对差之和。例如:给定a[]= {2,3, 5, 7 };输出将是(3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17。它必须比O(n^2)做得更好。原始数组不一定是排序的。

问求数组中每对整数的绝对差和
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问求数组中每对整数的绝对差和EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问求数组中每对整数的绝对差和
EN