Welches Array-Element hat die kleinste Summe absoluter Differenzen?

Hier sehen wir eine interessante Frage. Wir haben ein Array „a“, das N Elemente enthält. Wir müssen ein Element x finden, das den Wert von |a[0] - x| + |a[1] - x| + ... + |a[n-1] - x| minimiert. Dann müssen wir die minimierte Summe finden.

Angenommen, das Array ist: {1, 3, 9, 6, 3} und jetzt ist x 3. Die Summe beträgt also |1 - 3| + |9 - 3|.

Um dieses Problem zu lösen, müssen wir den Median des Arrays als x wählen. Wenn die Größe des Arrays gerade ist, gibt es zwei Medianwerte. Sie sind beide die beste Wahl für x.

Algorithmus

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

Beispiel

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

Ausgabe

Sum : 11

Das obige ist der detaillierte Inhalt vonWelches Array-Element hat die kleinste Summe absoluter Differenzen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!