Для такой последовательности, как S = {1,8,2,1,4,1,2,9,1,8,4}, мне нужно найти подпоследовательность минимальной длины, содержащую все элементы из S ( никаких дубликатов, порядок не имеет значения). Как найти эту подпоследовательность эффективным способом?
Примечание. В S есть 5 различных элементов: {1,2,4,8,9}. Подпоследовательность минимальной длины должна содержать все эти 5 элементов.
Алгоритм:
Сначала определите количество различных элементов в массиве - это можно легко сделать в линейном времени. Пусть существуют k разные элементы.
Выделите массив cur размером 10 ^ 5, каждый из которых показывает, сколько из каждого элемента используется в текущей подпоследовательности (см. ниже).
Удерживайте переменную cnt, показывая, сколько разных элементов в данный момент находится в рассматриваемой последовательности. Теперь возьмите два индекса, begin и end и проведите их по массиву следующим образом:
cnt и begin как 0, end как -1 (чтобы получить 0 после первого приращения). Затем, когда возможно выполнение:Если cnt != k:
2,1. приращение end. Если end уже есть конец массива, то перерыв. Если cur[array[end]] равно нулю, приращение cnt. Приращение cur[array[end]].
Else:
2.2 {
Попробуйте увеличить итератор begin: while cur[array[begin]] > 1, уменьшите его и увеличьте значение begin (cur[array[begin]] > 1 означает, что у нас есть другой такой элемент в нашей текущей подпоследовательности). В конце концов, сравните интервал [begin, end] с текущим ответом и сохраните его, если это будет лучше.
}
После того, как дальнейший процесс станет невозможным, вы получили ответ. Сложность - это O(n) - просто передача двух посредников через массив.
Реализация в С++:
#include <iostream>
using namespace std;
const int MAXSIZE = 10000;
int arr[ MAXSIZE ];
int cur[ MAXSIZE ];
int main ()
{
int n; // the size of array
// read n and the array
cin >> n;
for( int i = 0; i < n; ++i )
cin >> arr[ i ];
int k = 0;
for( int i = 0; i < n; ++i )
{
if( cur[ arr[ i ] ] == 0 )
++k;
++cur[ arr[ i ] ];
}
// now k is the number of distinct elements
memset( cur, 0, sizeof( cur )); // we need this array anew
int begin = 0, end = -1; // to make it 0 after first increment
int best = -1; // best answer currently found
int ansbegin, ansend; // interval of the best answer currently found
int cnt = 0; // distinct elements in current subsequence
while(1)
{
if( cnt < k )
{
++end;
if( end == n )
break;
if( cur[ arr[ end ]] == 0 )
++cnt; // this elements wasn't present in current subsequence;
++cur[ arr[ end ]];
continue;
}
// if we're here it means that [begin, end] interval contains all distinct elements
// try to shrink it from behind
while( cur[ arr[ begin ]] > 1 ) // we have another such element later in the subsequence
{
--cur[ arr[ begin ]];
++begin;
}
// now, compare [begin, end] with the best answer found yet
if( best == -1 || end - begin < best )
{
best = end - begin;
ansbegin = begin;
ansend = end;
}
// now increment the begin iterator to make cur < k and begin increasing the end iterator again
--cur[ arr[ begin]];
++begin;
--cnt;
}
// output the [ansbegin, ansend] interval as it the answer to the problem
cout << ansbegin << ' ' << ansend << endl;
for( int i = ansbegin; i <= ansend; ++i )
cout << arr[ i ] << ' ';
cout << endl;
return 0;
}
Вот алгоритм, который требует O (N) времени и O (N) пространства. Это похоже на то, что Григор Геворкян. Он также использует вспомогательный массив флагов O (N). Алгоритм находит самую длинную подпоследовательность уникальных элементов. Если bestLength < numUnique, то нет подпоследовательности, содержащей все уникальные элементы. Алгоритм предполагает, что элементы являются положительными числами и максимальный элемент меньше длины последовательности.
bool findLongestSequence() {
// Data (adapt as needed)
const int N = 13;
char flags[N];
int a[] = {1,8,2,1,4,1,2,9,1,8,1,4,1};
// Number of unique elements
int numUnique = 0;
for (int n = 0; n < N; ++n) flags[n] = 0; // clear flags
for (int n = 0; n < N; ++n) {
if (a[n] < 0 || a[n] >= N) return false; // assumptions violated
if (flags[a[n]] == 0) {
++numUnique;
flags[a[n]] = 1;
}
}
// Find the longest sequence ("best")
for (int n = 0; n < N; ++n) flags[n] = 0; // clear flags
int bestBegin = 0, bestLength = 0;
int begin = 0, end = 0, currLength = 0;
for (; begin < N; ++begin) {
while (end < N) {
if (flags[a[end]] == 0) {
++currLength;
flags[a[end]] = 1;
++end;
}
else {
break; // end-loop
}
}
if (currLength > bestLength) {
bestLength = currLength;
bestBegin = begin;
}
if (bestLength >= numUnique) {
break; // begin-loop
}
flags[a[begin]] = 0; // reset
--currLength;
}
cout << "numUnique = " << numUnique << endl;
cout << "bestBegin = " << bestBegin << endl;
cout << "bestLength = " << bestLength << endl;
return true; // longest subseqence found
}
У меня есть алгоритм O (N * M), где N - длина S, а M - количество элементов (оно, как правило, работает лучше при малых значениях M, т.е.: если имеется очень мало дубликатов, это может быть плохой алгоритм с квадратичной стоимостью). Edit: Кажется, что на самом деле он намного ближе к O (N) на практике. Вы получаете O(N*M) только в наихудших сценариях
Начнем с прохождения последовательности и записи всех элементов S. Пусть назовем это множество E.
Мы будем работать с динамической подпоследовательностью S. Создаем пустой map M, где M связывает каждому элементу количество раз, которое оно присутствует в подпоследовательности.
Например, если subSequence = {1,8,2,1,4} и E = {1, 2, 4, 8, 9}
M[9]==0M[2]==M[4]==M[8]==1M[1]==2Вам понадобится два индекса, каждый из которых будет указывать на элемент S. Один из них будет называться L, потому что он слева от подпоследовательности, образованной этими двумя индексами. Другой будет называться R как индекс правой части подпоследовательности.
Начните с инициализации L=0, R=0 и M[S[0]]++
Алгоритм:
While(M does not contain all the elements of E)
{
if(R is the end of S)
break
R++
M[S[R]]++
}
While(M contains all the elements of E)
{
if(the subsequence S[L->R] is the shortest one seen so far)
Record it
M[S[L]]--
L++
}
Чтобы проверить, содержит ли M все элементы E, вы можете иметь вектор булевых V. V[i]==true, если M[E[i]]>0 и V[i]==false, если M[E[i]]==0. Итак, вы начинаете с установки всех значений V в false, и каждый раз, когда вы делаете M[S[R]]++, вы можете установить V этого элемента в true, и каждый раз, когда вы выполняете M[S[L]]-- и M[S[L]]==0, тогда установите V этого элемента в false
Это можно решить с помощью динамического программирования.
На каждом шаге k мы вычисляем кратчайшую подпоследовательность, которая заканчивается на k -ой позиции S и которая удовлетворяет требованию содержать все уникальные элементы S.
Учитывая решение шага k (далее "последовательность" ), вычисление решения на этапе k+1 легко: добавьте (k+1) -ный элемент S к последовательности и затем удалите один за другим, все элементы в начале последовательности, которые содержатся в расширенной последовательности более одного раза.
Решение общей проблемы - это кратчайшая последовательность, найденная на любом из этапов.
Инициализация алгоритма состоит из двух этапов:
S один раз, создав алфавит уникальных значений.S; последней позицией этой последовательности будет начальное значение k.Все вышеизложенное может быть сделано в O(n logn) худшем случае (сообщите мне, если это потребует уточнения).
Вот полная реализация вышеуказанного алгоритма в Python:
import collections
S = [1,8,2,1,4,1,2,9,1,8,4,2,4]
# initialization: stage 1
alphabet = set(S) # the unique values ("symbols") in S
count = collections.defaultdict(int) # how many times each symbol appears in the sequence
# initialization: stage 2
start = 0
for end in xrange(len(S)):
count[S[end]] += 1
if len(count) == len(alphabet): # seen all the symbols yet?
break
end += 1
best_start = start
best_end = end
# the induction
while end < len(S):
count[S[end]] += 1
while count[S[start]] > 1:
count[S[start]] -= 1
start += 1
end += 1
if end - start < best_end - best_start: # new shortest sequence?
best_start = start
best_end = end
print S[best_start:best_end]
Примечания:
O(n) в худшем случае. Если это худший случай, о котором вы заботитесь, заменив их на древовидные структуры, даст общий O(n logn), который я обещал выше;S может быть устранено, что делает алгоритм подходящим для потоковой передачи данных;S являются малыми неотрицательными целыми числами, как показывают ваши комментарии, то count можно сгладить в целочисленный массив, доведя общую сложность до O(n).Если вам нужно делать это довольно часто для одной и той же последовательности и разных наборов, вы можете использовать для этого инвертированные списки. Вы готовите перевернутые списки для последовательности, а затем собираете все смещения. Затем сканируйте результаты из перевернутых списков для последовательности из последовательных чисел.
Если n длина последовательности и m размер запроса, подготовка будет в O(n). Время ответа для запроса будет в O(m^2), если я не ошибаюсь в шаге слияния.
Если вам нужна дополнительная информация, взгляните на статью Клаузена/Курта с 2004 года по алгебраическим базам данных ( " Поиск информации на основе контента по группам Теоретические методы" ). Это позволяет создать общую базу данных, которая может быть адаптирована к вашей задаче.
Я бы сказал:
Очевидно, что только элемент 3. сложный. Я бы использовал приоритетную очередь/кучу, которая назначает ключ каждому элементу из D и имеет элемент как значение. Помимо этого вам понадобится структура данных, которая сможет получить доступ к элементам в куче по их значению (карта w/указатели на элементы). Ключ всегда должен быть последней позицией в S, которая произошла с элементом.
Итак, вы проходите через S и для каждого прочитанного char вы делаете один из setKey O (log n), а затем смотрите на текущий min O (1) и записываете его в массив.
Должно быть O (n * log n). Надеюсь, я ничего не пропустил. Это пришло мне в голову, так что возьмите его с солью или позвольте сообществу указать на возможные ошибки, которые я мог бы сделать.
выше правильное решение и версия java выше кода
public class MinSequence {
public static void main(String[] args)
{
final int n; // the size of array
// read n and the array
final List<Integer> arr=new ArrayList<Integer>(4);
Map<Integer, Integer> cur = new TreeMap<Integer, Integer>();
arr.add(1);
arr.add(2);
arr.add(1);
arr.add(3);
int distinctcount=0;
for (final Integer integer : arr)
{
if(cur.get(integer)==null)
{
cur.put(integer, 1);
++distinctcount;
}else
{
cur.put(integer,cur.get(integer)+1);
}
}
// now k is the number of distinct elements
cur=new TreeMap<Integer,Integer>();
// memset( cur, 0, sizeof( cur )); // we need this array anew
int begin = 0, end = -1; // to make it 0 after first increment
int best = -1; // best answer currently found
int ansbegin = 0, ansend = 0; // interval of the best answer currently found
int cnt = 0; // distinct elements in current subsequence
final int inpsize = arr.size();
while(true)
{
if( cnt < distinctcount )
{
++end;
if (end == inpsize) {
break;
}
if( cur.get(arr.get(end)) == null ) {
++cnt;
cur.put(arr.get(end), 1);
} // this elements wasn't present in current subsequence;
else
{
cur.put(arr.get(end),cur.get(arr.get(end))+1);
}
continue;
}
// if we're here it means that [begin, end] interval contains all distinct elements
// try to shrink it from behind
while (cur.get(arr.get(begin)) != null && cur.get(arr.get(begin)) > 1) // we have another such element later in the subsequence
{
cur.put(arr.get(begin),cur.get(arr.get(begin))-1);
++begin;
}
// now, compare [begin, end] with the best answer found yet
if( best == -1 || end - begin < best )
{
best = end - begin;
ansbegin = begin;
ansend = end;
}
// now increment the begin iterator to make cur < k and begin increasing the end iterator again
if (cur.get(arr.get(begin)) != null) {
cur.put(arr.get(begin),cur.get(arr.get(begin))-1);
}
++begin;
--cnt;
}
// output the [ansbegin, ansend] interval as it the answer to the problem
System.out.println(ansbegin+"--->"+ansend);
for( int i = ansbegin; i <= ansend; ++i ) {
System.out.println(arr.get(i));
}
}