Блог

Главная - Вопросы по программированию - подсчитайте подмассивы с максимальным элементом как k

подсчитайте подмассивы с максимальным элементом как k

#python #optimization

#python #оптимизация

Вопрос:

Учитывая массив и число k, вам нужно подсчитать количество подмассивов, в которых k является максимальным.

Например, в массиве [4,1,2,3,1,5] и k=3. Таким образом, количество для этого массива будет равно 6.

Я пришел к следующему решению:

 count = 0
n = len(a)
for i in range(n):
  for j in range(i,n):
    b = a[i:j]
    if k in b and max(b) == k:
      count  = 1

return count

Временная сложность для этого равна O (n ^ 2). Как я могу оптимизировать его (предпочтительно используя подход с двумя указателями), чтобы получить решение O (n)?

Комментарии:

1. k Является уникальным в массиве или число может отображаться более одного раза?

2. В настоящее время я ищу решение, в котором k уникально. Но я был бы признателен за решение, которое будет работать, когда k встречается более одного раза

Ответ №1:

Одно решение для уникального k в списке:

 k = 3
a = [4,1,2,3,1,5]
length = len(a)
ucount, lcount = 0, 0

# Find the index of k:
index = a.index(k)

# From this position, go in one direction until a larger number is found
# increment ucount for each step
upper = index
while upper < length and a[upper] <= k:
    ucount  = 1
    upper  = 1

# After that, go from index backwards until a larger number is found
# increment lcount for each step
lower = index
while lower >= 0 and a[lower] <= k:
    lcount  = 1
    lower -= 1

# Multiply the upper and lower count
print(ucount*lcount)

В худшем случае это O (n) для нахождения индекса и O (n) снова для обоих циклов while вместе. Что в целом по-прежнему равно O (n).

Другим решением было бы собирать lower , index и upper при однократном обходе списка.

Для нескольких случаев k это становится более сложным, особенно когда они перекрываются (когда они соединены числами < k).