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

Question

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

Например: Дано a[]= {2,3, 5, 7 };

Выход

будет (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.

Это должно быть сделано лучше, чем O(n^2).

Исходный массив не обязательно отсортирован.

Answer 1

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

Answer 2

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

Вот код на C ++.

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

Answer 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

Answer 4

Просто альтернативный взгляд на это. Вот код Mathematica:

With[{n = Length@# - 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

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

Answer 5

Посмотрите на этот небольшой фрагмент рабочего кода в 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;
    }

}

Answer 6

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

Answer 7

Приведенный ниже код вычисляет a [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)).