Найти кратчайший путь в одном измерении

Question

В одномерном массиве S может быть любое количество элементов, принадлежащих набору

U:{A,B,C,D,E}  

, и повторение разрешено.
Пример:

S  = {E,B,D,C,A,D,A,E,E,D,B,B,A,C} 

Вопрос:

Каким самым эффективным способом я могу определить кратчайший диапазон / путь, который содержит все элементы, принадлежащие множеству U, в любом данном массиве S?имейте в виду, что массив не может быть отсортирован.

В приведенном выше примере самый короткий путь - это подключение первых 5 элементов массива S.

РЕДАКТИРОВАНИЕ:
1) Количество элементов множестваВы не постоянны.

Заранее спасибо.

Answer 1

Интересная домашняя работа, но вы все равно должны сами кодировать.

Хорошо, что вы не сказали нам, какой язык вы используете, поэтому я воспринимаю это как знак, так как вы решили сами написать код, которыйэто хорошо.

---

Моя лучшая попытка на данный момент:

Имеют 2 указателя для подстроки (диапазона), один для начала (меньший индекс)диапазон и один для end (больший индекс).Оба указателя сначала указывают на начало массива.

У вас есть список для , сколько ABCDE находятся в диапазоне соответственно.

Итерация end изслева направо.

Для каждого символа увеличивайте число для символа в списке.Если результат (увеличенный сколько )> 1 (посмотрите, если start указывает на тот же символ. Если да, переместите start вперед и минус 1, и) в то время как начало указывает на символ, соответствующий номер которого> 1, перемещается начало вперед и минус 1.

Если в списке все ABCDE> = 1,тогда мы нашли диапазон кандидатов.Сравните его с самой короткой длиной (если есть), и, если она меньше, обновите самую короткую длину и запишите индекс для начала нового самого короткого диапазона.

Answer 2

Сначала найдите различные элементы в массиве, который является O (n).Затем используйте метод скользящего окна, чтобы найти минимальный промежуток, в котором присутствуют все эти элементы.

Здесь вы можете увидеть как найти минимальное окно: http://tech -запросы.blogspot.com/2010/12/finding-minimum-window-in-array-which.html

Answer 3

Вот простой алгоритм, который сканирует массив один раз, постоянно проверяя, короче ли его видимый диапазон покрытия по сравнению с ранее видимыми диапазонами покрытия.

Для простоты я собираюсь предположить, что мы можем отобразитьA, B, C, D и E к целым числам 0-4, чтобы мы могли легко ссылаться на массив.Я не проверил это полностью, поэтому, пожалуйста, мысленно / фактически запустите его на примере или двух, чтобы убедиться, что он делает то, что вы хотите.

//Cell 0 is the last index at which we saw an A, cell 1 " " saw a B, etc.
int[] mostRecent = new int[U.length];
mostRecent.setAllValsTo(POSITIVE_INFINITY);

int shortestRange = POSITIVE_INFINITY; //We are trying to minimize this number.
int minIndex = 0; //The beginning index of the range
int maxIndex = POSITIVE_INFINITY; //The ending index of the range.

for(int i=0; i< S.length; i++) {
    int currentValue = S[i]; //This value will be 0-4, corresponding to A-E

    mostRecent[currentValue] = i;

    currentMax = mostRecent.findMax(); //beginning of current range
    currentMin = mostRecent.findMin(); //end of current range
    currentRange = currentMax - currentMin;

    if(currentRange < shortestRange) {
        shortestRange = currentRage;
        minIndex = currentMin;
        maxIndex = currentMax;
    }
}

//currentMax and currentMin now carry the starting and ending indices, use them as you see fit.
return shortestRange;

Это порядок O (nk), с n = Sдлина и k = длина U.Есть еще много оптимизаций, чтобы выжать из него, но я не знаю, смогу ли я снизить наихудший порядок.

Answer 4

Если я правильно понимаю проблему, я думаю, что вам нужно сделать (независимость от языка)

int partLen <- U.length;
do {
    Vector subSets <- S.partition(partLen);
    foreach set I in subSets
        if I.isEqualTo(U) then
            return true;
        else
            partLen <- partLen + 1;
} while (partLen <= S.length);
return false;

Где partition будет разбивать S на подмножества любой длины и isEqualTo может правильно сравнивать наборы.

Answer 5

Вот как бы я это сделал (в псевдокоде)

let counters[] be an array such that 
counters[j] = number of occurrences of character j, 
where j = 0 for 'A', j = 1 for 'B', etc.

build counters[] by scanning the original string s

let positions[j][] be an array listing the positions occupied by 
character j in the original string s; note the size of 
positions[j][] is equal to counters[j]

build positions[j][] by scanning the original string s;

let currentPositions[] be an array such that 
positions[j][currentPositions[j]] gives the position of the next 
occurrence of character j in the original string s

initially currentPositions[j] = 0 for every j = [0 .. u.length]

let bestLength = s.length
let bestMin = 0
let bestMax = 0
for i in [0 .. s.length] {
    for j in [0 .. u.length] {
        if ( 
          positions[i][currentPositions[i]] < i and 
          currentPositions[j] + 1 < counters[j]
        )
          currentPositions[j]++
    }
    let min = s.length
    int max = 0
    for j in [0 .. u.length] {
        curPos = positions[j][currentPositions[j]
        if (curPos > max) let max = curPos
        if (curPos < min) let min = curPos
    }
    if (max - min + 1 < bestLength) {
        let bestMin = min
        let bestMax = max
        let bestLength = max - min + 1
    }
}

the shortest path is that starting at bestMin, ending at bestMax, 
and having length bestLength

Сложность O (nk), где n = s.length и k = u.length