Поиск наиболее короткого среза в массиве со всеми уникальными значениями, как это сделать оптимальным образом?

Question

У меня есть массив, который содержит N элементов, значения которых находятся в диапазоне 0 <= значение <N и могут быть прерывистыми.Для этого массива мне нужно найти срез, который будет содержать все уникальные значения, и в то же время это будет самый короткий срез, который будет соответствовать вышеуказанному критерию. </p>

Пример, для массива {1, 2, 1, 2, 1, 4, 3, 4, 8, 1, 8} с 5 уникальными значениями {1, 2, 3, 4, 8} речь идет о срезе {2, 1, 4, 3, 4, 8}с длиной 6.

Есть ли оптимальный способ сделать это?На данный момент у меня наивная реализация, которая имеет слишком высокую сложность (вложенные циклы).Я пытался придумать идею для алгоритма, чтобы сделать это оптимальным образом, но, к сожалению, безрезультатно.На данный момент я пытался придумать что-то, что будет использовать вхождения для каждого уникального значения при циклическом просмотре массива, но все же мой разум недостаточно ясен.Любые идеи приветствуются, эта проблема беспокоит меня долгое время.:) Заранее спасибо.

С наилучшими пожеланиями

Answer 1

Первый прогон собирает возможные значения и создает карту с парами (value; counter = 0).Пусть N - это размер карты

. Для второго запуска подготовьте два индекса - left и right и ActiveCnt.

Move right, обновляя счетчики карт.При обновлении счетчика нуля увеличивается ActiveCnt.Когда ActiveCnt станет равным N, остановитесь.

Теперь двигайтесь left, уменьшая счетчики карт.Когда какой-то счетчик становится равным нулю, найдите разницу между right и left, сравните его с током MinLength, затем уменьшите ActiveCnt.Продолжить с индексом right и т. Д.