# 每個數組元素的最小絕對差之和 > 原文： [https://www.geeksforgeeks.org/sum-minimum-absolute-difference-array-element/](https://www.geeksforgeeks.org/sum-minimum-absolute-difference-array-element/) 給定 **n** 個不同整數的數組。 問題是找到每個數組元素的最小絕對差之和。 對于數組中索引為 **i** 的元素 **x** ，其最小絕對差的計算公式如下： **最小絕對差（x）** = min（abs （x – arr [j]）），其中 1 < = j < = n 且 j！= i， **abs** 是絕對值。 **輸入約束**： 2 < = n 例子： ``` Input : arr = {4, 1, 5} Output : 5 Sum of absolute differences is |4-5| + |1-4| + |5-4| Input : arr = {5, 10, 1, 4, 8, 7} Output : 9 Input : {12, 10, 15, 22, 21, 20, 1, 8, 9} Output : 18 ``` **樸素的方法**：使用兩個循環。 使用外循環選擇一個數組元素，并使用內循環計算與其余數組元素的絕對差。 找到最小絕對值并將其添加到總和中。 時間復雜度 `O(n^2)`。 **有效方法**：以下步驟是： 1. 對大小為 **n** 的數組進行排序。 2. 對于數組的**第一**元素，其最小絕對差是使用第二數組元素計算的。 3. 對于**最后一個**數組元素，其最小絕對差是使用倒數第二個數組元素計算的。 4. 對于其余數組元素 **1 < = i < = n-2** ，索引為 **i** 的元素的最小絕對差計算為： **minAbsDiff** = min（abs（arr [i] – arr [i-1]），abs（ar [i] – arr [i + 1]））。 ## C++ ```cpp // C++ implementation to find the sum of minimum? // absolute difference of each array element #include <bits/stdc++.h> using namespace std; // function to find the sum of? // minimum absolute difference int sumOfMinAbsDifferences(int arr[], int n) { ????// sort the given array ????sort(arr, arr+n); ????// initialize sum ????int sum = 0; ????// min absolute difference for ????// the 1st array element ????sum += abs(arr[0] - arr[1]); ????// min absolute difference for ????// the last array element ????sum += abs(arr[n-1] - arr[n-2]); ????// find min absolute difference for rest of the ????// array elements and add them to sum ????for (int i=1; i<n-1; i++) ????????sum += min(abs(arr[i] - arr[i-1]), abs(arr[i] - arr[i+1])); ????// required sum???? ????return sum;???? } // Driver program to test above int main() { ????int arr[] = {5, 10, 1, 4, 8, 7}; ????int n = sizeof(arr) / sizeof(arr[0]); ????cout << "Sum = " ?????????<< sumOfMinAbsDifferences(arr, n); }? ``` ## Java ```java // java implementation to find the sum // of minimum absolute difference of // each array element import java.*; import java.util.Arrays; public class GFG { ????// function to find the sum of? ????// minimum absolute difference ????static int sumOfMinAbsDifferences( ?????????????????????????int arr[] ,int n) ????{ ????????// sort the given array ????????Arrays.sort(arr); ????????// initialize sum ????????int sum = 0; ????????// min absolute difference for ????????// the 1st array element ????????sum += Math.abs(arr[0] - arr[1]); ????????// min absolute difference for ????????// the last array element ????????sum += Math.abs(arr[n-1] - arr[n-2]); ????????// find min absolute difference for ????????// rest of the array elements and? ????????// add them to sum ????????for (int i = 1; i < n - 1; i++) ????????????sum +=? ????????????Math.min(Math.abs(arr[i] - arr[i-1]), ????????????????????Math.abs(arr[i] - arr[i+1])); ????????// required sum? ????????return sum;? ????}????? ????// Driver code ????public static void main(String args[]) ????{ ????????int arr[] = {5, 10, 1, 4, 8, 7}; ????????int n = arr.length; ????????System.out.println( "Sum = " ????????+ sumOfMinAbsDifferences(arr, n)); ????} } // This code is contributed by Sam007\. ``` ## Python3 ```py # Python implementation to find the? # sum of minimum absolute difference? # of each array element # function to find the sum of? # minimum absolute difference def sumOfMinAbsDifferences(arr,n): ????# sort the given array ????arr.sort() ????# initialize sum ????sum = 0 ????# min absolute difference for ????# the 1st array element ????sum += abs(arr[0] - arr[1]); ????# min absolute difference for ????# the last array element ????sum += abs(arr[n - 1] - arr[n - 2]); ????# find min absolute difference for ????# rest of the array elements and ????# add them to sum ????for i in range(1, n - 1): ????????sum += min(abs(arr[i] - arr[i - 1]),? ??????????????????abs(arr[i] - arr[i + 1])) ????# required sum? ????return sum;? # Driver code arr = [5, 10, 1, 4, 8, 7] n = len(arr) print( "Sum = ", sumOfMinAbsDifferences(arr, n)) #This code is contributed by Sam007 ``` ## C# ```cs // C# implementation to find the sum // of minimum absolute difference of // each array element using System; public class GFG { ????// function to find the sum of? ????// minimum absolute difference ????static int sumOfMinAbsDifferences( ?????????????????????????int []arr ,int n) ????{ ????????// sort the given array ????????Array.Sort(arr); ????????// initialize sum ????????int sum = 0; ????????// min absolute difference for ????????// the 1st array element ????????sum += Math.Abs(arr[0] - arr[1]); ????????// min absolute difference for ????????// the last array element ????????sum += Math.Abs(arr[n-1] - arr[n-2]); ????????// find min absolute difference for ????????// rest of the array elements and ????????// add them to sum ????????for (int i = 1; i < n - 1; i++) ????????????sum +=? ????????????Math.Min(Math.Abs(arr[i] - arr[i-1]), ????????????????????Math.Abs(arr[i] - arr[i+1])); ????????// required sum? ????????return sum;? ????}????? ????// Driver code ????public static void Main () ????{ ????????int []arr = {5, 10, 1, 4, 8, 7}; ????????int n = arr.Length; ????????Console.Write( "Sum = " ????????+ sumOfMinAbsDifferences(arr, n)); ????} } // This code is contributed by Sam007\. ``` ## PHP ```php <?php // PHP implementation to find // the sum of minimum absolute // difference of each array element // function to find the sum of? // minimum absolute difference function sumOfMinAbsDifferences($arr, $n) { ????// sort the given array ????sort($arr); ????sort( $arr,$n); ????// initialize sum ????$sum = 0; ????// min absolute difference for ????// the 1st array element ????$sum += abs($arr[0] - $arr[1]); ????// min absolute difference for ????// the last array element ????$sum += abs($arr[$n - 1] - $arr[$n - 2]); ????// find min absolute difference ????// for rest of the array elements ????// and add them to sum ????for ($i = 1; $i < $n - 1; $i++) ????????$sum += min(abs($arr[$i] - $arr[$i - 1]),? ???????????????????abs($arr[$i] - $arr[$i + 1])); ????// required sum? ????return $sum;? } ????// Driver Code ????$arr = array(5, 10, 1, 4, 8, 7); ????$n = sizeof($arr); ????echo "Sum = ", sumOfMinAbsDifferences($arr, $n); // This code is contributed by nitin mittal. ?> ``` 輸出： ``` Sum = 9 ``` 時間復雜度：O（nlogn）