Phần tử mảng có tổng số chênh lệch tuyệt đối nhỏ nhất?

Ở đây chúng ta sẽ thấy một vấn đề thú vị. Chúng tôi đang lấy một mảng ‘a’ với N phần tử. Ta phải tìm một phần tử x sao cho | a [0] - x | + | a [1] - x | +… + | a [n-1] - x | được giảm thiểu. Sau đó, chúng ta phải tìm tổng nhỏ nhất.

Cho mảng là:{1, 3, 9, 6, 3} bây giờ x là 3. Vậy tổng là | 1 - 3 | + | 3 - 3 | + | 9 - 3 | + | 6 - 3 | + | 3 - 3 | =11.

Để giải quyết vấn đề này, chúng ta phải chọn trung vị của mảng là x. Nếu kích thước mảng là chẵn, thì hai giá trị trung vị sẽ ở đó. Cả hai đều sẽ là một lựa chọn tối ưu của x.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

Sum : 11