Как определить, существует ли среднее арифметическое число смежных элементов в отсортированном массиве, равное заданному значению, в наиболее эффективное время выполнения?

Question

ВХОД:

• Сортированный массив положительных, натуральных чисел,

ОЖИДАЕМАЯ СЛОЖНОСТЬ:

• Время: O(n)
• Дополнительное пространство: O(1)

Пример:

Входные данные :

arr = {2,3,17,30}x=10

Ожидаемое поведение:

Функция печатает индексы: 1,2 и возвращает истину, поскольку (3+17)/2 = x = 10

Входные данные :

x = 30

Ожидаемое поведение:

Функция напечатает индекс 3 и вернет true, так как (30)/1 = х = 30`

Мой подход к алгоритму:

мы возьмем среднее арифметическое, начиная с первого элемента в массиве. Если x больше нашего результата, мы добавим следующий элемент в массиве к среднему арифметическому. Иначе мы вычтем первый элемент из среднего арифметического.

Я попробовал это, и это не сработало. Может кто-нибудь мне помочь?

Answer 1

1. Найти наибольшее k, для которого сумма a0+a1+a2+...+ak <= k*target
2. Если сумма == k* цель - хорошо
3. Если sum!= K *target - добавить следующий элемент, а затем вычитать первые элементы, пока среднее значение не станет меньше или равно цели.

Если ваш k достигает длины массива, решения нет. Еще у вас есть решение. Сложность O(n), как если бы на шаге 3 вы добавляли только одно число, так как предыдущая сумма + ak+1 была больше, чем k * target, и вы можете перемещать только левую границу только n раз.

1. proc(array, x):
2.     sum = 0;
3.     left = 0;
4.     right = 0;
5.     do:
6.         sum += array[right];
7.         right++;
8.     while (sum+array[right] <= (right+1)*target && right<array.size);
9.     if (sum == right*target):
10.        for (i = left; i < right; i++):
11.            print(array[i] + <sep>);
12.        end_for
13.        return;
14.    end_if
15.    while (left <= right):
16.        if (right<array.size): sum += array[right++];
17.        do:
18.            sum-=array[left++]
19.        while (sum > target*(right-left));
20.        if (sum == target*(right-left)):
21.            for (i = left; i < right; i++):
22.                print(array[i] + <sep>);
23.            end_for
24.            return;
25.        end_if
26.    end_while
27.end_proc

Правильно работает для массивов с положительными числами. Небольшие модификации требуются для негативов, но на собеседованиях они часто спрашивают о массивах со всеми числами положительными. Некоторые дополнительные условия эвакуации могут потребоваться, если нет правильного решения.

Answer 2

Если мы рассчитали среднее значение k элементы from 0 to k, что мы можем сказать о среднем from 1 to kили о from 0 to k + 1? Оба средних 1 to k а также 0 to k + 1 равны или больше среднего первого k elemnts. Зачем? Переход от подмножества from 0 to k подмножество from 1 to k, означает удаление наименьшего элемента, поэтому не может уменьшить общее среднее. Переход от подмножества from 0 to k подмножество from 0 to k + 1, означает добавление элемента, который не меньше любого другого, поэтому он не может уменьшить общее среднее значение.

Мы знаем, какое число из данного массива должно быть частью результата? Да, это последний меньше или равен цели. Зачем? Когда он равен, тогда мы закончим. Когда он не равен, тогда нам нужно иметь как большие, так и более низкие элементы.

Затем мы сохраняем среднее значение, увеличивая его, добавляя элементы с правой стороны и уменьшая с левой стороны.

public static int[] findMean(int[] input, int target) {
    int firstGreater = 0;
    int n = input.length;
    while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead!
    if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1};
    int left = firstGreater - 1, right = firstGreater;
    long sum = input[left];
    while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) {
        if((right - left) * target > sum) sum += input[right++];
        else sum += input[--left];
    }
    if((right - left) * target != sum) {
        left = right = -1;
    }
    return new int[]{left, right - 1};
}