Блог

В одномерном массиве 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) Количество элементов множества U не является постоянным.

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

Интересное домашнее задание, но вам все равно придется кодировать самостоятельно.

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

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

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

Составьте список того, сколько ABCDEв диапазоне соответственно.

Повторите конец слева направо.

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

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

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

 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 может корректно сравнивать наборы.

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

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

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

Для простоты я собираюсь предположить, что мы можем сопоставить 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. Есть еще много оптимизаций, которые можно выжать из этого, но я не знаю, смогу ли я снизить порядок наихудшего случая.

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

 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.длина и k = u.длина