C++で絶対差の合計が最小となる配列要素を求める方法

このプログラムは、重複しない要素からなる配列が与えられたときに、各要素の絶対差の合計が最小となる値を求めるものです。この概念をより深く理解するために、まず必要な基礎知識をおさらいしましょう。

配列（Array）とは、同じデータ型の要素を格納するためのコンテナです。配列の長さは事前に定義しておく必要があります。

絶対差（Absolute Difference）とは、2つの数値の差の絶対値のことです。つまり、差は常に正の値となり、負の値は正の値に変換されます。

各要素について最小絶対差を求め、その合計を計算します。最小絶対差の公式は次のとおりです。

Minimum Absolute Difference (a) = min(abs(a – arr[j]));

ここで、1 <= j <= n かつ j != i であり、abs は絶対値を表します。

入力: arr = {1, 3, 9, 3, 6}
出力: 8

解説

最適な解は x = 3 を選択することです。この場合、合計は次のように計算されます。

|1 – 3| + |3 – 3| + |9 – 3| + |3 – 3| = 2 + 0 + 6 + 0 = 8

アルゴリズム

• 与えられた入力配列をソートします。

• 配列の先頭要素の最小絶対差は、2番目の要素を使って計算します。

• 配列の末尾要素の最小絶対差も、後ろから2番目の要素を使って計算します。

• その他のインデックス i の位置にある要素の最小絶対差は、次の式で求めます。

• minAbsDiff = min( abs(arr[i] – arr[i-1]), abs(arr[i] – arr[i+1]) )

サンプルコード

#include<iostream>
#include <algorithm>
using namespace std;
int abs_sum(int a[], int len);
int main() {
   int a[]={1, 3, 9, 3, 6};
   int n, i;
   n=5;
   sort(a, a+n);
   int sum = 0;
   sum += abs(a[0]- a[1]);
   sum += abs(a[n-1]-a[n-2]);
   for (int i = 1; i < n-1; i++) {
      sum += min(abs(a[i]-a[i-1]), abs(a[i]-a[i+1]));
   }
   cout<<"The element with minimum sum of absolute differences is : "<<sum;
   return 0;
}

出力結果

The element with minimum sum of absolute differences is : 8

このように、配列をソートした上で隣接する要素同士を比較することで、各要素の最小絶対差を効率よく求め、その合計である 8 を得ることができます。