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

Question

ВХОД:

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

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

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

Пример:

Входной сигнал:

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

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

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

Вход:

x = 30

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

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

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

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

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

Answer 1

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

Если ваш k достигает длины массива, никакого решения. Иначе у вас есть решение. Сложность O (n), как если бы на шаге 3 вы добавляли только одно число, поскольку предыдущая сумма + ak + 1 была больше цели k *, и вы можете перемещать только левую границу только 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}; 
}