絶対差の合計が最小の配列要素？

ここで、1つの興味深い問題が発生します。 N個の要素を持つ1つの配列「a」を使用しています。 | a [0]--x|となるような要素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として選択する必要があります。配列サイズが偶数の場合、2つの中央値があります。どちらも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