Оптимизация этого решения: самая длинная последовательность последовательных целых чисел

Question

Пример ввода:

5
1
2
1
3
1

Первое число = количество членов в наборе, N

После N номеров = идентификаторы членов

Я бы хотелчтобы найти размер самой длинной последовательной последовательности различных целых чисел в наборе.В этом случае это будет последовательность {2, 1, 3}, поэтому на выходе получится 3.

Мое решение по грубой силе - создать скользящее окно, которое уменьшается в размере на 1 каждыйитерация.Начальный размер - это размер ввода.Так, для примера ввода, он сначала оценил бы {1, 2, 1, 3, 1}, если набор не все уникален, затем уменьшил бы окно до 4 и оценил {1, 2, 1, 3},{2, 1, 3, 1}.Продолжайте, пока не найдете уникальный набор.

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

Answer 1

Вы можете использовать хеш-таблицу для решения O(N). Проще говоря, отслеживайте последний индекс каждого уникального элемента и последний раз, когда повторение происходит. Максимум между этими двумя переменными в каждом индексе показывает, насколько далеко вы можете вернуться к этому индексу без повторения.

Для полноты картины приведем прямую и (надеюсь) хорошо прокомментированную реализацию Python:

def longestDistinctSequence(iterable):

    res = 0
    # store the indices of each unique element
    hashmap = {}
    # keep track of how back you can go before you run into a repetition
    last_repeat = 0

    # loop through each index and item
    for index, item in enumerate(iterable):

        # how back you can go before you can run into a repetition is the max of:
        #     1. The last occurence of this element (zero if this is first instance)
        #     2. The last_repeat of the last iteration
        last_repeat = max(hashmap.get(item, 0), last_repeat)

        # calculate the global maximum
        res = max(res, index - last_repeat + 1)

        # update the hashmap to reflect the repetition of this element
        hashmap[item] = index + 1

    return res