minimum-absolute-sum-difference

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 two positive integer arrays <code>nums1</code> and <code>nums2</code>, both of length <code>n</code>.

The absolute sum difference of arrays <code>nums1</code> and <code>nums2</code> is defined as the sum of <code>|nums1[i] - nums2[i]|</code> for each <code>0 &lt;= i &lt; n</code> (0-indexed).

You can replace at most one element of <code>nums1</code> with any other element in <code>nums1</code> to minimize the absolute sum difference.

Return the minimum absolute sum difference after replacing at most one element in the array <code>nums1</code>. Since the answer may be large, return it modulo <code>109 + 7</code>.

<code>|x|</code> is defined as:

<ul>
	<li><code>x</code> if <code>x &gt;= 0</code>, or</li>
	<li><code>-x</code> if <code>x &lt; 0</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] =&gt; [1,1,5], or
- Replace the second element with the third: [1,7,5] =&gt; [1,5,5].
Both will yield an absolute sum difference of <code>|1-2| + (|1-3| or |5-3|) + |5-5| = </code>3.
</pre>

Example 2:

<pre>
Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0
Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an 
absolute sum difference of 0.
</pre>

Example 3:

<pre>
Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] =&gt; [10,10,4,4,2,7].
This yields an absolute sum difference of <code>|10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20</code>
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums1.length</code></li>
	<li><code>n == nums2.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 105</code></li>
</ul>

minAbsoluteSumDiff

Minimum Absolute Sum Difference

Minimum Sum of Squared Difference

minimum-sum-of-squared-difference

最小差值平方和

Minimize the Maximum Adjacent Element Difference

minimize-the-maximum-adjacent-element-difference

最小化相邻元素的最大差值

Array

Binary Search

Ordered Set

Sorting

给你两个正整数数组 <code>nums1</code> 和 <code>nums2</code> ，数组的长度都是 <code>n</code> 。

数组 <code>nums1</code> 和 <code>nums2</code> 的 绝对差值和 定义为所有 <code>|nums1[i] - nums2[i]|</code>（<code>0 <= i < n</code>）的 总和（下标从 0 开始）。

你可以选用 <code>nums1</code> 中的 任意一个 元素来替换 <code>nums1</code> 中的 至多 一个元素，以 最小化 绝对差值和。

在替换数组 <code>nums1</code> 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 <code>109 + 7</code> 取余 后返回。

<code>|x|</code> 定义为：

<ul>
	<li>如果 <code>x >= 0</code> ，值为 <code>x</code> ，或者</li>
	<li>如果 <code>x <= 0</code> ，值为 <code>-x</code></li>
</ul>

 

示例 1：

<pre>
输入：nums1 = [1,7,5], nums2 = [2,3,5]
输出：3
解释：有两种可能的最优方案：
- 将第二个元素替换为第一个元素：[1,7,5] => [1,1,5] ，或者
- 将第二个元素替换为第三个元素：[1,7,5] => [1,5,5]
两种方案的绝对差值和都是 <code>|1-2| + (|1-3| 或者 |5-3|) + |5-5| = </code>3
</pre>

示例 2：

<pre>
输入：nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
输出：0
解释：nums1 和 nums2 相等，所以不用替换元素。绝对差值和为 0
</pre>

示例 3：

<pre>
输入：nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
输出：20
解释：将第一个元素替换为第二个元素：[1,10,4,4,2,7] => [10,10,4,4,2,7]
绝对差值和为 <code>|10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20</code>
</pre>

 

提示：

<ul>
	<li><code>n == nums1.length</code></li>
	<li><code>n == nums2.length</code></li>
	<li><code>1 <= n <= 105</code></li>
	<li><code>1 <= nums1[i], nums2[i] <= 105</code></li>
</ul>