具有最小绝对差之和的数组元素？

在这里，我们将看到一个有趣的问题。我们采用一个包含N个元素的数组'a'。我们必须找到一个元素x使得| a [0]-x | + | a [1]-x | +…+ | a [n-1]-x | 被最小化。然后，我们必须找到最小化的总和。

令数组为：{1，3，9，6，3}现在x为3。所以总和为| 1-3 |。+ | 3 -3 | + | 9 -3 | + | 6 -3 | + | 3 -3 | = 11。

为了解决这个问题，我们必须选择数组的中位数为x。如果数组大小为偶数，则将有两个中值。它们都是x的最佳选择。

算法

minSum(arr,n)

begin
   sort array arr
   sum := 0
   med := median of arr
   for each element e in arr, do
      sum := sum + |e - med|
   done
   return sum
end

示例

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minSum(int arr[], int n){
   sort(arr, arr + n);
   int sum = 0;
   int med = arr[n/2];
   for(int i = 0; i<n; i++){
      sum += abs(arr[i] - med);
   }
   return sum;
}
int main() {
   int arr[5] = {1, 3, 9, 6, 3};
   int n = 5;
   cout << "Sum : " << minSum(arr, n);
}

输出结果

Sum : 11