Найти кратчайший подмассив, содержащий все элементы

Question

Предположим, у вас есть массив чисел и другой набор чисел.Вы должны найти кратчайший подмассив, содержащий все числа с минимальной сложностью.

Массив может иметь дубликаты, и давайте предположим, что набор чисел не имеет.Это не заказано - подмассив может содержать набор номера в любом порядке.

Например:

Array: 1 2 5 8 7 6 2 6 5 3 8 5
Numbers: 5 7

Тогда самым коротким подмассивом, очевидно, будет Array[2:5] (нотация Python).

Кроме того, что бы вы сделали, если хотите избежать сортировкимассив по какой-то причине (а-ля онлайн алгоритмы)?

Answer 1

Доказательство решения с линейным временем

Я напишу правое расширение , означающее увеличение правой конечной точки диапазона на 1, и левое сокращение означать увеличение левой конечной точки диапазона на 1. Этот ответ является небольшим отклонением ответа Аасмунда Элдхусета .Разница здесь в том, что как только мы найдем наименьшее j такое, что [0, j] содержит все интересные числа, мы будем рассматривать только диапазоны, которые содержат все интересные числа.(Можно интерпретировать ответ Aasmund таким образом, но также можно интерпретировать его как допускающее потерю одного интересного числа из-за сжатия влево - алгоритм, правильность которого еще предстоит установить.)

Основная идея заключается в том, что для каждой позиции j мы найдем самый короткий удовлетворяющий диапазон, заканчивающийся в позиции j, учитывая, что мы знаем самый короткий удовлетворяющий диапазон, заканчивающийся в позиции j-1.

РЕДАКТИРОВАТЬ: Исправлен сбой в базовом случае.

Базовый случай: найдите наименьшее j 'такое, что [0, j'] содержит все интересные числа.По построению не может быть диапазонов [0, k наименьший наибольший i такой, что [i, j '] содержит все интересные числа (т. Е. Удерживайте j' фиксированным).Это наименьший удовлетворяющий диапазон, заканчивающийся в позиции j '.

Чтобы найти наименьший удовлетворяющий диапазон, заканчивающийся в любой произвольной позиции j, мы можем расширить самый маленький удовлетворяющий диапазон, заканчивающийся в позиции j-1, на 1 позицию.Этот диапазон также обязательно будет содержать все интересные числа, хотя он может быть не минимальной длины. Тот факт, что мы уже знаем, что это удовлетворительный диапазон, означает, что нам не нужно беспокоиться о расширении диапазона «назад» влево, поскольку это может только увеличить диапазон на его минимальную длину (т.е. принять решениехуже.Таким образом, левая конечная точка диапазона должна быть продвинута как можно дальше, пока это свойство выполняется.Когда больше никаких сокращений влево не может быть выполнено, у нас есть диапазон удовлетворения минимальной длины, заканчивающийся на j (поскольку дальнейшие сокращения влево явно не могут сделать диапазон удовлетворяющим снова), и мы закончили.

Поскольку мы выполняем этодля каждой крайней правой позиции j мы можем взять диапазон минимальной длины по всем крайним правым позициям, чтобы найти общий минимум.Это можно сделать, используя вложенный цикл, в котором j продвигается в каждом цикле внешнего цикла.Ясно, что j продвигается в 1 n раз.Поскольку в любой момент времени нам когда-либо понадобится только крайняя левая позиция наилучшего диапазона для предыдущего значения j, мы можем сохранить его в i и просто обновить его по ходу работы.i начинается с 0, всегда <= j <= n, и только когда-либо продвигается вверх на 1, что означает, что он может продвигаться не более n раз.И i, и j продвигаются не более n раз, что означает, что алгоритм имеет линейное время. </p>

В следующем псевдокоде я объединил обе фазы в один цикл.Мы только пытаемся сжать левую сторону, если мы достигли стадии наличия всех интересных чисел:

# x[0..m-1] is the array of interesting numbers.
# Load them into a hash/dictionary:
For i from 0 to m-1:
    isInteresting[x[i]] = 1

i = 0
nDistinctInteresting = 0
minRange = infinity
For j from 0 to n-1:
    If count[a[j]] == 0 and isInteresting[a[j]]:
        nDistinctInteresting++
    count[a[j]]++

    If nDistinctInteresting == m:
        # We are in phase 2: contract the left side as far as possible
        While count[a[i]] > 1 or not isInteresting[a[i]]:
            count[a[i]]--
            i++

        If j - i < minRange:
            (minI, minJ) = (i, j)

count[] и isInteresting[] - хэши / словари (или простые массивы, если задействованные числа маленькие).

Answer 2

Это звучит как проблема, которая хорошо подходит для подхода скользящее окно : сохранить окно (подрешетка), которое постепенно расширяется и сжимается, и использовать хэш-карту для отслеживать количество раз, когда каждое «интересное» число встречается в окне. Например. начните с пустого окна, затем разверните его, включив в него только элемент 0, затем элементы 0-1, затем 0-2, 0-3 и т. д., добавив последующие элементы (и используя хэш-карту для отслеживания существующих номеров. в окне). Когда хэш-карта сообщает вам, что в окне существуют все интересные числа, вы можете начать сокращать их: например, 0-5, 1-5, 2-5 и т. Д., Пока не обнаружите, что в окне больше нет всех интересных чисел. Затем вы можете снова развернуть его на правой стороне и так далее. Я вполне (но не полностью) уверен, что это сработает для вашей проблемы, и его можно реализовать для работы за линейное время.

Answer 3

Это решение определенно не выполняется за время O (n), как предложено некоторыми из псевдокода выше, однако это реальный (Python) код, который решает проблему, и, по моим оценкам, работает в O (n ^ 2):

def small_sub(A, B):
    len_A = len(A)
    len_B = len(B)

    sub_A = []
    sub_size = -1
    dict_b = {}

    for elem in B:
        if elem in dict_b:
            dict_b[elem] += 1
        else:
            dict_b.update({elem: 1})

    for i in range(0, len_A - len_B + 1):
        if A[i] in dict_b:
            temp_size, temp_sub = find_sub(A[i:], dict_b.copy())

            if (sub_size == -1 or (temp_size != -1 and temp_size < sub_size)):
                sub_A = temp_sub
                sub_size = temp_size

    return sub_size, sub_A

def find_sub(A, dict_b):
    index = 0
    for i in A:
        if len(dict_b) == 0:
            break

        if i in dict_b:
            dict_b[i] -= 1

            if dict_b[i] <= 0:
                del(dict_b[i])

        index += 1

    if len(dict_b) > 0:
        return -1, {}
    else:
        return index, A[0:index]

Answer 4

Скажем, массив имеет n элементов, а set содержит m элементов

Sort the array, noting the reverse index (position in the original array)
// O (n log n) time

for each element in given set
   find it in the array
// O (m log n) time  - log n for binary serch, m times

keep track of the minimum and maximum index for each found element

min - max определяет ваш диапазон

Общая сложность времени: O ((m + n) log n)