минимальное положение среза - алгоритм порядка N

Question

Дается непустой нуль-индексированный массив A, состоящий из N целых чисел. Пара целых чисел (P, Q), такая, что 0 ≤ P < Q < N, называется срезом массива A (обратите внимание, что срез содержит как минимум два элемента). Среднее значение среза (P, Q) представляет собой сумму A [P] + A [P + 1] + ... + A [Q], деленную на длину фрагмента . Если быть точным, среднее равно (A [P] + A [P + 1] + ... + A [Q])/(Q - P + 1).

Написать функцию:

Int решение (интермедиат А [], Int N);

, что при заданном непустовом нулевом индексированном массиве A, состоящем из N целых чисел, возвращает начальную позицию среза с минимальным средним значением. Если имеется более одного среза с минимальным средним значением, вы должны вернуть наименьшую начальную позицию такого среза.

Предположим, что:

N представляет собой целое число в диапазоне [2..100,000]; каждый элемент массива A является целым числом в диапазоне [-10,000..10,000]. Сложность:

Ожидаемая наихудшая временная сложность - O (N); Ожидаемая наихудшая сложность пространства - это O (N), за пределами хранения ввода (не считая хранения, необходимого для входных аргументов).

Можете ли вы публиковать только решения только с заказами N?

Answer 1

Если A имел только положительные числа, вы могли бы уйти с этим:

pos = 0 
min_avg = A[0] + A[1] 
for (i=2; i<N; i++) 
    m = A[i-1] + A[i] 
    if (m < min_avg) 
     min_avg = m 
     pos = i-1 
return pos 

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

Если А имеет отрицательные числа, вы можете настроить все значения вверх первым:

offset = min(A) 
for (i=0; i<N; i++) 
    A[i] -= offset 

В сочетании с предыдущим алгоритмом:

offset = min(A) * 2    (because we're adding two numbers below) 
pos = 0 
min_avg = A[0] + A[1] - offset 
for (i=2; i<N; i++) 
    m = A[i-1] + A[i] - offset 
    if (m < min_avg) 
     min_avg = m 
     pos = i-1 
return pos 

Answer 2

Я думаю, что вы правы, лучшее, что я могу сделать представляет собой O (N 2 ) решение (это в Python):

from random import randint 

N = 1000 
A = [randint(-10000, 10000) for _ in xrange(N)] 

def solution(A, N): 
    min_avg = 10001 
    for p in xrange(N): 
     s = A[p] 
     for q in xrange(1,N-p): 
      s += A[p+q] 
      a = s/(q+1.) 
      if a < min_avg: 
       min_avg = a 
       pos = (p, q+1) 
    return pos 

print solution(A, N) 

Однако средние значения больших ломтиков имеют тенденцию к среднему (среднему) значению исходного диапазона. В этом случае среднее значение равно нулю, на полпути между -10000 и 10000. В большинстве случаев наименьшее среднее имеет срез из двух значений, но иногда это может быть срез из трех значений и редко может быть еще больше значений , Поэтому я думаю, что мой предыдущий ответ работает в большинстве (> 90%) случаев. Это действительно зависит от значений данных.