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

本文将探讨一个有趣的题目。我们将采用一个包含 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 浏览次数

开启你的 职业

完成课程以获得认证

立即开始