Нахождение размера «кратчайшего диапазона индексов», который просматривает все уникальные пути

Question

Учитывая массив String, находим размер ' кратчайшего диапазона индексов ', который просматривает весь уникальный путь.

Пример, A = { E, R, E, R, A, R, T, A }, должно быть 5 .Как мы видим, диапазоны A[2] = E and A[6] = T содержат все уникальные пути.(В этом случае E, R, A, T)

Я могу решить с помощью нескольких циклов, как показано ниже.(решено Kotlin.)

fun problem(array: Array<String>): Int {
    if (array.isEmpty()) return 0
    val unique = array.distinct()
    var result = 200000
    for (i in 0 until A.size) {
        val tempSet = HashSet<String>()
        val remaining = A.sliceArray(i until array.size)
        var count = 0

        while (true) {
            tempSet.add(remaining[count])
            if (unique.size == tempSet.size) break
            count++

            if (count == remaining.size) {
                count = 200000
                break
            }
        }

        result = Math.min(result, count + 1)
    }

    return result
}

Но когда приходит большой массив (около 100 000), я не знаю, как сократить время.Как я могу это сделать?

Некоторые контрольные примеры:

1. [E, R, E, R, A, R, T, A] -> 5. Потому что [2..6] содержит все уникальные пути.(E, R, A, T)

2. [C, A, A, R, C, A, A, R] -> 3. Поскольку [3..5] содержитвсем уникальный путь.(C, A, R)

3. [R, T, A, R, A, R, E, R] -> 6. Поскольку [1..6] содержит все уникальныедорожка.(T, A, R, E)

4. [A, R, R, C, T, E, A, R] -> 5. Поскольку [2..6] содержитвсем уникальный путь.(R, C, T, E, A)

Answer 1

Эту проблему можно эффективно решить с помощью подхода с двумя указателями.

Сделать структуру словаря, содержащую char в качестве ключа и counter в качестве значения (в простейшем случае - массив int)

Установите два индекса L и R в 0.

Переместите R вправо, для текущего счетчика приращения символа соответствующего элемента dict.Когда размер dict (в случае массива - число ненулевых элементов) становится равным unique, стоп

Теперь переместите L вправо для текущего счетчика декремента соответствующего элемента dict, удаляя элемент, когда счетчик становитсянуль.Когда размер dict становится меньше, чем unique, остановитесь.На последнем шаге интервал L..R содержит все возможные элементы.

Продолжите с R и т. Д.

Выберите самый короткий интервал во время сканирования.

Код Python для аналогичного вопроса здесь

Answer 2

Фраза «весь уникальный путь» я буду интерпретировать как «все возможные значения».

Для строки длиной n с k уникальными значениями это можно решить за время O(n log(k)), используя как словарь, так и очередь с приоритетами. Ключевые идеи таковы:

1. На первом проходе найти все возможные значения.
2. Во второй раз сохраняйте словарь most_recently_found, где каждое значение было найдено последним.
3. Сохранять приоритетную очередь longest_since, значение которой было самым длинным с момента его обнаружения.
4. Сохраняйте минимальный пробег самого короткого промежутка.

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

most_recently_found[current_value] = current_position
oldest = longest_since.top()
if current_value == oldest.value:
    while oldest.position() != most_recently_found[oldest.position()]:
        longest_since.pop()
        longest_since.push({value: top.value, position: most_recently_found[oldest.position()]
        oldest = longest_since.top()
if current_position - oldest.position() < best_gap:
    best_gap = current_position - oldest.position()

Дело в том, что для каждого найденного значения вам необходимо обновить словарь (O(1)), возможно, придется удалить его из очереди приоритетов (O(k)), возможно, придется добавить что-то новое в очередь приоритетов ( O(k)) и, возможно, придется сделать некоторую арифметику (O(1)). Отсюда O(n log(k)) для всего.