Сложность, которой я должен придерживаться, равна o(n), поэтому мне не разрешено использовать вложенные циклы. У меня есть приблизительное представление о том, что я хочу сделать, однако я не уверен, как сохранить нижнюю границу диапазона. Цель состоит в том, чтобы найти нижнюю границу интервала, содержащего наибольшее количество элементов. Обозначим L как длину диапазона. Что я пробовал:
lst = [1,2,3,4,5,5,6,6,6,12] #after sorting by radix
L = 3
for i in range(len(lst)):
lower_bound[i] = i
upper_bound[i] = i + L #in this case L = 3.
#if i is in range of certain i and its upper_bound,
#increment count for that interval
# e.g. 1 is in range of 0-3, so count for lower_bound[1] will +1.
# e.g. 6 is in range of 4-6, so count for lower_bound[4] will +3.
#return the lower_bound with max count
Таким образом, для этого примера будет возвращено 3, поскольку 3-6 имеет 7 элементов (приоритет отдается минимальной нижней границе). Я не уверен, что это правильный подход :( Это выглядит правильно, учитывая сложность o (n)?
