sum-of-absolute-differences-in-a-sorted-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code> sorted in non-decreasing order.

Build and return an integer array <code>result</code> with the same length as <code>nums</code> such that <code>result[i]</code> is equal to the summation of absolute differences between <code>nums[i]</code> and all the other elements in the array.

In other words, <code>result[i]</code> is equal to <code>sum(|nums[i]-nums[j]|)</code> where <code>0 &lt;= j &lt; nums.length</code> and <code>j != i</code> (0-indexed).

&nbsp;
Example 1:

<pre>
Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.
</pre>

Example 2:

<pre>
Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= nums[i + 1] &lt;= 104</code></li>
</ul>

getSumAbsoluteDifferences

Sum of Absolute Differences in a Sorted Array

Array

Math

Prefix Sum

给你一个 非递减 有序整数数组 <code>nums</code> 。

请你建立并返回一个整数数组 <code>result</code>，它跟 <code>nums</code> 长度相同，且<code>result[i]</code> 等于 <code>nums[i]</code> 与数组中所有其他元素差的绝对值之和。

换句话说， <code>result[i]</code> 等于 <code>sum(|nums[i]-nums[j]|)</code> ，其中 <code>0 <= j < nums.length</code> 且 <code>j != i</code> （下标从 0 开始）。

 

示例 1：

<pre>
输入：nums = [2,3,5]
输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
</pre>

示例 2：

<pre>
输入：nums = [1,4,6,8,10]
输出：[24,15,13,15,21]
</pre>

 

提示：

<ul>
	<li><code>2 <= nums.length <= 105</code></li>
	<li><code>1 <= nums[i] <= nums[i + 1] <= 104</code></li>
</ul>