絶対差の合計が最も小さい配列要素はどれですか?

ここで、興味深い質問を見てみましょう。 N 個の要素を含む配列 'a' があります。 |a[0] - x| |a[1] - x| ... |a[n-1] - x| の値を最小にする要素 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

以上が絶対差の合計が最も小さい配列要素はどれですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。