Самый короткий подмассив, содержащий все элементы без использования массивов?

Question

Проблема: Найти длину кратчайшего подмассива, содержащего все элементы Пример: 1 2 2 3 2 2 1 3 Ответ: 3

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

Answer 1

Я предполагаю, что причина, по которой вы хотите избежать массива, заключается в том, что вы хотите написать идиоматический код ML, и поэтому предпочли бы использовать чисто функциональную структуру данных, а не изменяемый массив?

Если это так, то вы можете использовать чисто функциональное красно-черное дерево для подхода "скользящего окна" почти точно так же, как вы бы использовали массив;единственные различия:

• Вместо O (1) поисков у вас есть O (log m ) поисков, где m - количество различных элементов.
• Вместо мутаций O (1) у вас есть O (log m *)1025 *) преобразования, где преобразование возвращает измененную копию карты (совместно используя большинство ее узлов).

Answer 2

Я не понимаю вашу проблему с массивами. Вы не указываете, какой язык семейства ML вы используете, но Ocaml (мой любимый), безусловно, имеет массивы. Если вам действительно не нравятся массивы по религиозным причинам, вы всегда можете использовать карту с целочисленными ключами, которая выполняет те же функции, что и массив, но намного медленнее.