Определите, какие элементы последовательности A можно использовать для создания данной последовательности B за линейное ⇐ C++

[Anonymous]

Предположим, у нас есть последовательность A и подпоследовательность A, называемая B. Мне нужно определить, какие элементы последовательности A потенциально могут быть использованы для построения подпоследовательности B.
Например, предположим, что A = [1, 3, 2, 1, 2, 3, 1, 3, 2] и B = [1, 3, 1, 2]
Чтобы построить B из A мы могли бы использовать элементы по индексам:

• 1, 2, 4, 5
• 1, 2, 4, 9
• 1, 2, 7, 9
• 1, 6, 7, 9

Таким образом, наш ответ должен выглядеть так: [истина, правда, ложь, правда, правда, правда, правда, ложь, правда], где true означает, что возможно, что элемент с i-м индексом использовался для построения подпоследовательности B.
Это было бы легко решить с помощью O(2^N * M) временная сложность (сгенерируйте все подпоследовательности A и сравните их с B). Но мне нужно решение, которое работает примерно так: O(NlogN).
Я нашел решение, которое работает, когда все элементы A (так что B > также) уникальны.
Я перебираю A и для каждого i-го элемента проверяю:
< ол>
[*]

Код: Выделить всё

A[i]

существует в B, иначе мы можем отбросить этот i-й элемент
[*]Предположим, j равен индексу, где A[ i] был найден в B. Проверяем, i >= j, иначе мы можем отбросить этот i-й элемент, потому что если j > i, то наша подпоследовательность не будет поддерживать порядок
[*]Мы проверяем, есть ли какой-либо сосед B[j], чтобы B[j - 1] или B[j + 1] находился справа от A[ i] (все элементы, индексы которых больше i). Теперь, поскольку элементы уникальны, мы можем сказать, что этот конкретный элемент A должен был использоваться в некоторой позиции B[j], потому что всегда будет один элемент A. подпоследовательность, равная B.

Вот как это может выглядеть в коде:

Код: Выделить всё

#include 
#include 
#include 

using namespace std;

bool val_exists(const vector
>& A_val_sorted, int val, int min_idx) {
if (val == -1) {
return true;
}

if (min_idx == A_val_sorted.size())
return false;

int l = 0;
int r = A_val_sorted.size() - 1;

while (l = min_idx)
return true;

l = mid + 1;
}
else if (A_val_sorted[mid].first < val) {
l = mid + 1;
}
else {
r = mid - 1;
}
}

return false;
}

int main()
{
int n, m;
cin >> n >> m;

// val, original index
vector A_val_sorted(n);
vector B_val_sorted(m);

vector A(m);

for (int i = 0; i < n; ++i) {
cin >> A_val_sorted[i].first;
A_val_sorted[i].second = i;
}

for (int i = 0; i < m; ++i) {
cin >> B_val_sorted[i].first;
B_val_sorted[i].second = i;

A[i] = B_val_sorted[i].first;
}

sort(A_val_sorted.begin(), A_val_sorted.end());
sort(B_val_sorted.begin(), B_val_sorted.end());

vector result(n);
for (const pair& b : A_val_sorted) {
int val = b.first;
int idx = b.second;

int l = 0;
int r = m - 1;
bool valid = false;
while (l 

Подробнее здесь: [url]https://stackoverflow.com/questions/78722490/determine-which-elements-of-sequence-a-can-be-used-to-create-given-sequence-b-in[/url]