절대 차이의 합이 가장 작은 배열 요소는 무엇입니까?

여기에서 흥미로운 질문을 보게 됩니다. N개의 요소를 포함하는 배열 'a'가 있습니다. |a[0] - x| + |a[1] - x| + ... + |a[n-1] - x|의 값을 최소화하는 요소 x를 찾아야 합니다. 그런 다음 최소화된 합을 찾아야 합니다.

배열이 {1, 3, 9, 6, 3}이고 이제 x가 3이라고 가정합니다. 따라서 합계는 |1 - 3| + |3 - 3| + |6 - 3|

이 문제를 해결하려면 배열의 중앙값을 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

위 내용은 절대 차이의 합이 가장 작은 배열 요소는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!