具有最小絕對差和的陣列元素？

本文將探討一個有趣的題目。我們將採用一個包含 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

Arnab Chakraborty

更新於：02-Jul-2020

319 瀏覽次數

開啟你的 職業

完成課程以獲得認證

立即開始