# 兩個數組對的絕對差的最小和 > 原文： [https://www.geeksforgeeks.org/minimum-sum-absolute-difference-pairs-two-arrays/](https://www.geeksforgeeks.org/minimum-sum-absolute-difference-pairs-two-arrays/) 給定兩個數組 ***a []*** 和 ***b []*** 等長 ***n*** 。 任務是將數組 ***a*** 的每個元素與數組 ***b*** 中的元素配對，以使總和 *****的 S***** 對的絕對差最小。 假設有兩個元素 **a [ *i* ]** 和 **a [ *j* ]** **（ *i* ！= *j* 的** **a** 與元素 **b [ *p* ]** 和 **b 配對 [ *q* ]** ，分別為 ***b*** ， ，然后 ***p*** 不等于 ***q*** 。 **示例**： ``` Input : a[] = {3, 2, 1} b[] = {2, 1, 3} Output : 0 Input : n = 4 a[] = {4, 1, 8, 7} b[] = {2, 3, 6, 5} Output : 6 ``` 解決問題的方法是簡單的貪婪方法。 它由**兩個**步驟組成。 **步驟 1** ：以 **`O(N log N)`**時間對兩個數組進行排序。 **步驟 2** ：找出兩個數組的每對**對應元素** *（元素在相同索引處）*的絕對差，并將結果加到總和[ ***S*** 。 該步驟的時間復雜度為 **`O(n)`**。 因此，程序的整體時間復雜度為 **`O(N log N)`**。 ## C++ ```cpp // C++ program to find minimum sum of absolute // differences of two arrays. #include <bits/stdc++.h> using namespace std; // Returns minimum possible pairwise absolute // difference of two arrays. long long int findMinSum(int a[], int b[], int n) { ????// Sort both arrays ????sort(a, a+n); ????sort(b, b+n); ????// Find sum of absolute differences ????long long int sum= 0 ; ????for (int i=0; i<n; i++) ????????sum = sum + abs(a[i]-b[i]); ????return sum; } // Driver code int main() { ????// Both a[] and b[] must be of same size. ????long long int a[] = {4, 1, 8, 7}; ????long long int b[] = {2, 3, 6, 5}; ????int n = sizeof(a)/sizeof(a[0]); ????printf("%lld\n", findMinSum(a, b, n)); ????return 0; } ``` ## Java ```java // Java program to find minimum sum of // absolute differences of two arrays. import java.util.Arrays; class MinSum { ????// Returns minimum possible pairwise? ????// absolute difference of two arrays. ????static long findMinSum(long a[], long b[], long n) ????{ ????????// Sort both arrays ????????Arrays.sort(a); ????????Arrays.sort(b); ????????// Find sum of absolute differences ????????long sum = 0 ; ????????for (int i = 0; i < n; i++) ????????????sum = sum + Math.abs(a[i] - b[i]); ????????return sum; ????} ????// Driver code ????public static void main(String[] args)? ????{ ????????// Both a[] and b[] must be of same size. ????????long a[] = {4, 1, 8, 7}; ????????long b[] = {2, 3, 6, 5}; ????????int n = a.length; ????????System.out.println(findMinSum(a, b, n)); ????}???? } // This code is contributed by Raghav Sharma ``` ## Python3 ```py # Python3 program to find minimum sum? # of absolute differences of two arrays. def findMinSum(a, b, n): ????# Sort both arrays ????a.sort() ????b.sort() ????# Find sum of absolute differences ????sum = 0 ????for i in range(n): ????????sum = sum + abs(a[i] - b[i]) ????return sum # Driver program # Both a[] and b[] must be of same size. a = [4, 1, 8, 7] b = [2, 3, 6, 5] n = len(a) print(findMinSum(a, b, n)) # This code is contributed by Anant Agarwal. ``` ## C# ```cs // C# program to find minimum sum of // absolute differences of two arrays. using System; class MinSum { ????// Returns minimum possible pairwise? ????// absolute difference of two arrays. ????static long findMinSum(long []a, long []b, ???????????????????????????long n) ????{ ????????// Sort both arrays ????????Array.Sort(a); ????????Array.Sort(b); ????????// Find sum of absolute differences ????????long sum = 0 ; ????????for (int i = 0; i < n; i++) ????????????sum = sum + Math.Abs(a[i] - b[i]); ????????return sum; ????} ????// Driver code ????public static void Main(String[] args)? ????{ ????????// Both a[] and b[] must be of same size. ????????long []a = {4, 1, 8, 7}; ????????long []b = {2, 3, 6, 5}; ????????int n = a.Length; ????????Console.Write(findMinSum(a, b, n)); ????}? } // This code is contributed by parashar... ``` ## PHP ```php <?php // PHP program to find minimum sum? // of absolute differences of two? // arrays. // Returns minimum possible pairwise // absolute difference of two arrays. function findMinSum($a, $b, $n) { ????// Sort both arrays ????sort($a);? ????sort($a, $n); ????sort($b);? ????sort($b, $n); ????// Find sum of absolute? ????// differences ????$sum= 0 ; ????for ($i = 0; $i < $n; $i++) ????????$sum = $sum + abs($a[$i] -? ??????????????????????????$b[$i]); ????return $sum; } ????// Driver Code ????// Both a[] and b[] must ????// be of same size. ????$a = array(4, 1, 8, 7); ????$b = array(2, 3, 6, 5); ????$n = sizeof($a); ????echo(findMinSum($a, $b, $n)); // This code is contributed by nitin mittal. ?> ``` Output : ``` 6 ```