Unsur tatasusunan yang manakah mempunyai jumlah perbezaan mutlak terkecil?

Di sini, kita akan melihat soalan yang menarik. Kami mempunyai tatasusunan 'a' yang mengandungi elemen N. Kita perlu mencari unsur x yang meminimumkan nilai |a[0] - x| + |a[1] - x| + ... + |a[n-1] - x|. Kemudian kita perlu mencari jumlah minimum.

Katakan tatasusunan ialah: {1, 3, 9, 6, 3}, dan sekarang x ialah 3. Jadi jumlahnya ialah |1 - 3|.

Untuk menyelesaikan masalah ini, kita perlu memilih median tatasusunan sebagai x. Jika saiz tatasusunan adalah genap, akan terdapat dua nilai median. Mereka semua adalah pilihan terbaik untuk x.

Algoritma

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

Contoh

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

Output

Sum : 11

Atas ialah kandungan terperinci Unsur tatasusunan yang manakah mempunyai jumlah perbezaan mutlak terkecil?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!