Алгоритм нахождения длины минимального подмассива, содержащего все элементы массива / вектора - PullRequest
Новая
       33

Алгоритм нахождения длины минимального подмассива, содержащего все элементы массива / вектора

0 голосов
/ 07 июля 2019

Допустим, у нас есть массив {7, 3, 7, 3, 1, 3, 4, 1}.Что мне нужно, так это алгоритм (предпочтительно некоторый пример кода C ++), который будет возвращать длину минимального подмассива, который содержит все элементы массива .

В этом случае это будет 5: {7, 3, 1, 3, 4}, и это самый короткий подмассив исходного массива, который содержит все элементы массива, которые равны 1,3, 4 и 7.

Кроме того, еще один пример массива {2, 1, 1, 3, 2, 1, 1, 3} и алгоритм должен возвращать 3, так как искомый массив мы ищемis {1, 3, 2} (индексы 2-4 исходного массива).

Я нашел здесь похожий вопрос: Найти минимальную длину подсписка, содержащего все элементы списка но это не похоже на ответ.

Подпись функции должна быть такой: int algorithm(std::vector<int> &arr){...}

1 Ответ

2 голосов
/ 07 июля 2019

Найти последний подмассив в O (n):

Например, для массива [1, 2, 3, 2, 2, 1, 1] получить количество элементов в хэш-таблице / карте (или массиве длямаленький диапазон): { 1: 3, 2: 3, 3: 1 }

Чтобы найти начальный индекс подмассива, начните с первого значения в массиве и проверьте, является ли его число больше 1. Если это число больше 1, уменьшите егосчитать на единицу и переходить к следующему значению до значения со счетом 1. Повторите то же самое в обратном направлении, чтобы найти последний индекс подмассива: 

1, 2, 3, 2, 2, 1, 1
      ^        ^

Найти остальные подмассивы в O(n):

Теперь, чтобы проверить, является ли это минимальным подмассивом, проверьте наличие подмассивов перед ним.Для этого ищите перед первым индексом последний индекс значения 1, который находится в последнем индексе.Если он найден, измените на него первый индекс и уменьшите последний индекс на единицу: 

1, 2, 3, 2, 2, 1, 1
^           ^

Теперь, чтобы найти последний индекс нового подмассива, ищите значение между первым и последним индексом для значения.2, который находится в последнем индексе, и измените последний индекс на него: 

1, 2, 3, 2, 2, 1, 1
^        ^

Повторяйте, пока не будет найдено значение последнего индекса между первым и последним индексом: 

1, 2, 3, 2, 2, 1, 1
^     ^

Теперь проверьте, меньше ли счетчик нового подмассива, чем у предыдущего подмассива, и при необходимости обновите индексы текущего минимального подмассива.

Поиск остальных подмассивов необходимо повторитьпока значение последнего индекса не может быть найдено до первого индекса.

...