Поиск суммы абсолютной разницы каждой пары целых чисел из массива

Ответ 1

обратите внимание, что вы добавляете каждое число ровно в k раз (где k - его место, если вы сортируете список) Кроме того, вы вычитаете каждое число точно n-1-k раз Вы можете отсортировать список (O (nlogn)) и затем перебрать отсортированный массив, умножив каждый элемент, как указано выше.

Ответ 2

Я думаю, что нашел ответ. Я получил его, посмотрев выражение в моем сообщении.

Вот код в С++.

int AbsDiff(int a[], int n)
{
  if ( n < 2 ) return 0;
  sort(a,a+n);     
  int sum = 0;
  int i;
  for(i=n-1;i>=0;i--)
  {
    sum += (a[i]*(i) - a[i]*(n-i-1));
  }
  return sum;
}

Ответ 3

Например: с учетом [] = {2,3, 5, 7};
(3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.

Я полагаю, вы могли

• Суммируйте умножение каждого числа, начиная назад С#count - 1, чтобы получить общее количество
• Суммируйте умножение каждого числа, начиная С#count - 1, чтобы получить итоговое значение для вычитания

Тогда это станет (7*3 + 5*2 +3*1) - (2*3 + 3*2 + 5*1) = 17

Ответ 4

Просто альтернативная перспектива. Вот код Mathematica:

With[{n = [email protected]# - 1}, Range[-n, n, 2].Sort[#]] & 

n= один меньше длины списка

Range[-n, n, 2] создает список с номерами от -n до n с шагом 2, например. Range[-4, 4, 2]= {-4, -2, 0, 2, 4}

. представляет собой векторный точечный продукт, например. {a, b, c} . {x, y, z}= a x + b y + c z

Sort просто сортируется.

Итак, для вашего примера мы имеем: {-3, -1, 1, 3} . {2, 3, 5, 7}= 17

Вот график длины списка в зависимости от времени:

Ответ 5

В приведенном ниже коде вычисляется значение [0] (- 3) + a [1] (- 1) + a [2] (1) + a [3] (3), если размер массива = 4.

result := 0
for i := 0 to sizeof(a)-1 do
begin
   result := result + a[i] * (i*2 - sizeof(a) + 1)
end

Если вам нужно иметь дело с отсортированным массивом, вы можете сначала отсортировать его по алгоритму быстрой сортировки с сложностью O (n * log (n)).

Ответ 6

Я думаю, что мне немного поздно публиковать это, но я думаю, что эта программа CPP должна работать.

//JUST LIKE ANIMALS !!!!

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll funcy(ll a[], ll n)
{

ll sum = 0;
ll i;
for(i=0;i<n;i++)
{
sum += (a[i]*(i) - a[i]*(n-i-1));
}
return sum;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll i,n;cin>>n;ll v[n+1];
for(i=0;i<n;i++)cin>>v[i];
sort(&v[0],&v[n]);
cout<<AbsDiff(v,n);
return 0;

}

P.s. При условии n > 2. Пожалуйста, если в этом что-то не так, не стесняйтесь меня исправить.

Ответ 7

Посмотрите на этот небольшой кусок рабочего кода в JAVA. Надеюсь, что это помогает и имеет смысл.

import java.util.Arrays;

public class PairDifference {

    public static void main(String[] args) {
        int[] arr = {2,3,5,7};
        System.out.println(getPairDifference(arr));
    }

    static int getPairDifference(int[] a){
        int diff = 0;
        Arrays.sort(a);
        int n = a.length;
        for(int i=0; i<n; i++)
            diff += (a[i]*i) - (a[n-1-i]*i);

        return diff;
    }

}