Нахождение подмассива с минимальным диапазоном - PullRequest
Новая
       28

Нахождение подмассива с минимальным диапазоном

0 голосов
/ 15 января 2020

Учитывая массив из N натуральных чисел в диапазоне от индекса 0 до N - 1, как я могу найти непрерывный подмассив длины K с минимально возможным диапазоном. Другими словами, max (subarray) - min (subarray) минимизируется. Если есть несколько ответов, любой подойдет.

Например, найдите подмассив длины 2 с наименьшим диапазоном из [4, 1, 2, 6]

Ответ будет [ 1, 2] при 2 - 1 = 1 дает наименьший диапазон из всех возможных смежных подмассивов.

Другие подмассивы: [4, 1] (диапазон 3), [2, 6] (диапазон 4)

Я использую python, и до сих пор я пробовал линейный искать с помощью функций min () max (), и это не кажется эффективным. Я думал об использовании minheap, но я не уверен, как бы вы это реализовали, и я даже не уверен, сработает ли это. Любая помощь будет высоко ценится.

редактировать: код добавлен 

# N = length of array_of_heights, K = subarray length
N, K = map(int, input().split(' '))
array_of_heights = [int(i) for i in input().split(' ')]



min_min = 100000000000000000000

# iterates through all subarrays in the array_of_heights of length K
for i in range(N + 1 - K):
    subarray = land[i : i + K]
    min_min = min(max(subarray)-min(subarray), min_min)

print(min_min)

Ответы [ 2 ]

1 голос
/ 15 января 2020

Существует алгоритм линейного времени O(N) для получения минимума или максимума в движущемся окне указанного размера (в то время как ваша реализация имеет O(N*K) сложность)

Использование deque из В модуле collections вы можете реализовать два параллельных запроса, сохраняя минимальное и максимальное значения для текущей позиции окна и извлекая лучшую разницу после единственного обхода списка. 

import collections

def mindiff(a, k):
    dqmin = collections.deque()
    dqmax = collections.deque()
    best = 100000000
    for i in range(len(a)):
        if len(dqmin) > 0 and dqmin[0] <= i - k:
            dqmin.popleft()
        while len(dqmin) > 0 and a[dqmin[-1]] > a[i]:
            dqmin.pop()
        dqmin.append(i)
        if len(dqmax) > 0 and dqmax[0] <= i - k:
            dqmax.popleft()
        while len(dqmax) > 0 and a[dqmax[-1]] < a[i]:
            dqmax.pop()
        dqmax.append(i)
        if i >= k - 1:
            best = min(best, a[dqmax[0]]-a[dqmin[0]])
    return best

print(mindiff([4, 1, 2, 6], 2))
1 голос
/ 15 января 2020

Вы можете использовать numpy для улучшения времени выполнения.

Пример: 

def f1(l,k):
    subs = np.array([l[i:i+k] for i in range(len(l)-k+1)])
    return np.min(subs.max(axis=1) - subs.min(axis=1))

Малый тест (f2 ваша функция здесь). 

>>> arr = np.random.randint(100,size=10000)
>>> timeit.timeit("f1(arr,4)",setup="from __main__ import f1,f2,np,arr",number=1)
0.01172515214420855
>>> timeit.timeit("f2(arr,4)",setup="from __main__ import f1,f2,np,arr",number=1)
14.226237731054425
...