Этот пост обрабатывает извлечение среза, подмножества, которое показывает минимальное среднее значение, из числового списка.
Описание задания
Дан непустой массив 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).
Например, массив A такой, что:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
содержит следующие примеры фрагментов:
- срез (1, 2), среднее значение которого равно (2 + 2)/2 = 2;
- срез (3, 4), среднее значение которого равно (5 + 1)/2 = 3;
- срез (1, 4), среднее значение которого равно (2 + 2 + 5 + 1) / 4 = 2,5.
Цель состоит в том, чтобы найти начальную позицию среза, среднее значение которого минимально.
Напишите функцию:
защитное решение (A)
что для заданного непустого массива A, состоящего из N целых чисел, возвращается начальная позиция среза с минимальным средним значением. Если имеется более одного среза с минимальным средним значением, следует вернуть наименьшую начальную позицию такого среза.
Например, дан массив A такой, что:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
функция должна возвращать 1, как описано выше.
Напишите эффективный алгоритм для следующих предположений:
- N — целое число в диапазоне [2..100 000];
- каждый элемент массива A является целым числом в диапазоне [−10 000..10 000].
Авторские права, 2009–2021 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.
Ключевой момент
- На уроке Codility важно свести к минимуму вычислительную сложность.
- Насколько это возможно, полезно избегать команды цикла.
- Кроме того, математические знания помогают сделать решения более действенными.
Решение (с использованием Python)
def min_check(avg_min, avg_tmp, idx_min, idx_tmp):
if(avg_tmp < avg_min): return idx_tmp, avg_tmp
else: return idx_min, avg_min
def solution(A):
idx_max = len(A)+1
idx_min, avg_min = 0, sum(A[0:2])/2
if(idx_max == 2): return idx_min
for idx in range(3, idx_max):
idx2, idx3 = idx-2, idx-3
avg_tmp2 = sum(A[idx2:idx])/2
avg_tmp3 = sum(A[idx3:idx])/3
idx_min, avg_min = min_check(avg_min, avg_tmp2, idx_min, idx2)
idx_min, avg_min = min_check(avg_min, avg_tmp3, idx_min, idx3)
return idx_min
Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.
