Задача известна как Longest Consecutive Sequence
Имеется массив неотсортированных чисел, возможны дубли
Найти самую длинную непрерывную последовательность, сортировать исходные данные нельзя.
Пример:
num = [1, 6, 10, 4, 7, 8, 3]
Решение: 6, 7, 8
Пока у меня самое быстрое решение со следующим алгоритмом:
строится хеш-таблица - или словарь - по следующему правилу - по шагам итерации:
i: 1 Table: {1=1}
i: 6 Table: {1=1, 6=6}
i: 10 Table: {1=1, 6=6, 10=10}
i: 4 Table: {1=1, 4=4, 6=6, 10=10}
i: 7 Table: {1=1, 4=4, 6=7, 7=6, 10=10}
i: 8 Table: {1=1, 4=4, 6=8, 7=6, 8=6, 10=10}
Т.е. время равно O(n). плюс накладные расходы на память того же порядка
Другие варианты, которые не используют дополнительную память, например попытка динамически удалять элементы подмассивов, тормозят
Вопрос: есть что-либо более другое, более быстрое ?