0

Добрый вечер, Уважаемые хэшкодовцы!

Предлагаю немного подумать над оптимальным решением такой вот задачки: нужно найти сумму разностей всех элементов в упорядоченном массиве.

Поясню на примере: у нас есть массив [-3 5 10], тогда сумма разностей всех его элементов будет = (5+3) + (10+3) + (10-5) = 26

Естественно, самый простой алгоритм, который приходит в голову, это:

        long sum = 0;
        for (int i = 0; i < arr.length()-1; i++)
            for (int j = i+1; j <= arr.length()-1; j++) {
                sum += arr[j] - arr[i];
            }

Но как вы понимаете, он в то же время и самый медленный... Нужно что-то более оптимальное! Какие будут мысли по этому поводу?

2
  • Разность не коммутативная операция. Вы наверное имели ввиду (-3-5) + (-3-10) + (5-10) = -26?
    – a_gura
    18 апр 2013 в 20:27
  • Нет, суммируются именно разности "следующих" элементов с "предыдущим" - так, как я описал в примере.
    – Rams666
    18 апр 2013 в 20:34

2 ответа 2

7

Можно сделать за один проход.

Пусть наша последовательность a[0], a[1], ..., a[n-1]. Мысленно выпишем все разности:

a[1] - a[0]
a[2] - a[0]
...
a[n-1] - a[0]
a[2] - a[1]
...

Подсчитаем, сколько раз у нас входит a[i] с плюсом, а сколько — с минусом для произвольного i. Выпишем те разности, в которых фигурирует a[i]:

a[i] - a[0]
a[i] - a[1]
...
a[i] - a[i-1]
a[i+1] - a[i]
a[i+2] - a[i]
...
a[n-1] - a[i]

Мы видим, что с плюсом оно входит ровно i раз, а с минусом — (n-1) - (i+1) + 1 = n - i - 1 раз. Получается, для a[i] надо взять коэффициент i - n + i + 1 = 2 * i - n + 1.

Решение:

long sum = 0, n = arr.length();
for (int i = 0; i < n; i++)
    sum += (2 * i - n + 1) * arr[i];
3
  • Превосходный ответ!
    – Rams666
    18 апр 2013 в 22:27
  • @Rams666: спасибо!
    – VladD
    19 апр 2013 в 0:03
  • Ответ @a_gura появился практически одновременно, и содержит по сути то же вычисление.
    – VladD
    19 апр 2013 в 0:05
7

Если выписать сумму, как функцию от n-парметров, то получим (n1 - n0) + (n2 - n0) + (n2 - n1). Видно, что каждый элемент повторяется несколько раз как есть и несколько раз, как обратная по знаку величина. Отсюда решение за один проход по массиву:

    int[] arr = new int[]{-3, 5, 10};
    int m = arr.length;
    int res = 0;
    for (int i = 0; i < m; i++) {
        res += arr[i] * i - arr[i] * (m - (i + 1));
    }
    System.out.println(res);

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.