Нахождение самого маленького окна

Question

Нахождение самого маленького окна

Учитывая два массива A[n] и B[m], как я могу найти самое маленькое окно в A это содержит все элементы B.

Я пытаюсь решить эту проблему в O (n) время, но у меня есть проблема при выполнении его. Есть ли, любой хорошо знает алгоритм или процедуру решения его.

5

c++ c algorithm

задан Mark Elliot 21 June 2010 в 03:20

2 ответа

Если m > n, A не может содержать все элементы B (и, следовательно, у нас есть O(1) решение).

Иначе:

Создать хэш-таблицу, отображающую элементы B на последовательность {0..m-1} (это O(n), так как m <= n).
Создайте массив C[m] для подсчета случаев появления членов B (инициализируйте в 0) в текущем окне.
Создайте переменную z для подсчета количества 0 элементов C (инициализируйте в m).
Создайте переменные s и e для обозначения начала и конца текущего окна
while e < n:
- Если z ненулевое, увеличиваем e и обновляем C и z. O(1)
- иначе рассматриваем это окно как возможное решение (т.е. если оно минимально, сохраняем его), затем инкрементируем s и обновляем C и z. O(1)

Можно показать, что цикл while имеет не более 2n итераций. Так что все это O(n), я думаю.

4

ответ дан 14 December 2019 в 08:42

Другие вопросы по тегам:

c++ c algorithm

Похожие вопросы:

score 3 · Accepted Answer

countНазовем окно "минимальным", если его нельзя уменьшить. Т.е. после увеличения левой или уменьшения правой границы оно перестает быть действительным окном (не содержит всех элементов из B). В вашем примере их три: [0, 2], [2, 6], [6, 7]

Предположим, что вы уже нашли самое левое минимальное окно [left, right]. ([0, 2] в вашем примере) Теперь мы просто сдвинем его вправо.

// count[x] tells how many times number 'x'
// happens between 'left' and 'right' in 'A'
while (right < N - 1) {
    // move right border by 1
    ++right;
    if (A[right] is in B) {
        ++count[A[right]];
    }

    // check if we can move left border now
    while (count[A[left]] > 1) {
        --count[A[left]];
        ++left;
    }

    // check if current window is optimal
    if (right - left + 1 < currentMin) {
        currentMin = right - left + 1;
    }
}

Это скольжение работает, потому что разные "минимальные" окна не могут содержать друг друга.