Найдите кратчайшие подпоследовательности A[0:L], B[0:L], где M различных элементов в A больше, чем M различных элементов в B (сложность по времени)

Мне нужно найти минимальный подпорядок размера L, A[0:L], B[0:L], такой что есть M различных элементов в A, которые больше M различных элементов в B. Например, A[i] > B[j] учитывается, но я не могу использовать A[i] или B[j] снова. Также подпорядки должны начинаться с начала массива.

Домашнее задание связано с AVLTrees и Heap, так что я предполагаю, что решение будет включать одно из них (для примера ниже я использовал priority_queue из stl, но на самом деле мне не разрешено использовать какие-либо контейнеры из библиотек, поэтому у меня уже есть реализация мин-кучи, но для простоты понимания я использовал эквивалент из stl). Также ожидается, что я решу вопрос, используя AVL Tree или Heap.

Ps. Я узнал, что массивы могут содержать дубликаты.

Размер A и B одинаковый, который составляет: N.

Мне нужно найти решение с временной сложностью O(N * logN * logM)

#include <iostream>
#include <queue>
#include <span>

int minLenOfSubarrays(std::span<int> aArr, std::span<int> bArr, int M)
{
    const int N = aArr.size();
    int count = 0;
    int L = 0;

    int left = M;
    int right = N;
    while(left <= right){ //log N
        //Heap a; //мин-куча
        //Heap b; //мин-куча
        int mid = left+(right-left)/2;
        std::priority_queue<int,std::vector<int>,std::greater<int>> a;
        std::priority_queue<int,std::vector<int>,std::greater<int>> b;
        count = 0;
        for(int j = 0; j < mid; j++){ //N log N
            a.push(aArr[j]);
            b.push(bArr[j]);
        }
        while(!a.empty()){ // N log N
            if(a.top() > b.top()){
                count++;
                a.pop();
                b.pop();
            }
            else{
                a.pop();
            }
        }
        if(count >= M){
            L = mid;
            right = mid-1;
        }
        else{
            left = mid+1;
        }
    }
    return L;
}

int main(int argc, char* argv[]){

    int aArr[] = {2,4,10,6,1,11};
    int bArr[] = {3,5,8,9,7,12};
    int M = 3;

    std::cout << minLenOfSubbarays(aArr, bArr, M) << '\n';
}

Я пробовал решение, используя мин-кучи и двоичный поиск, но сложность, которую я смог достичь, составляет максимум O(N*logN*logN).

В вашем двоичном поиске для каждого mid выполните следующее:

1. Выявите M наибольших значений в A[0:L] (в порядке возрастания). Это можно сделать за O(L * logM), что также O(N * logM), с помощью AVL дерева или кучи.
2. Выявите M наименьших значений в B[0:L] (в порядке возрастания). Снова O(N * logM).
3. Параллельно пройдите по ним, проверяя, является ли каждое значение A больше значения B. Это занимает O(M) и также O(N).

Двоичный поиск добавляет оставшийся множитель logN.

Бонус: Вы можете сделать это O(N * logN), отсортировав все значения A и B перед двоичным поиском, а затем для каждого mid получить M префиксных значений A и M префиксных значений B, фильтруя уже отсортированные значения. В “исполняемом псевдокоде”:

from bisect import bisect

A = 2,4,10,6,1,11
B = 3,5,8,9,7,12
M = 3

# Сортируем индексы по их значениям
N = len(A)
Ai = sorted(range(N), key=A.__getitem__)
Bi = sorted(range(N), key=B.__getitem__)

# Проверяем, имеют ли A[:L] и B[:L] желаемое свойство 
def enough(L):
    largeA = [A[i] for i in Ai if i < L][-M:]
    smallB = [B[i] for i in Bi if i < L][:M]
    return all(a > b for a, b in zip(largeA, smallB))

# Двоичный поиск, нахождение наименьшего L от M до N, который достаточен
print(bisect(range(N), False, M, N, key=enough))

(Это предполагает, что всегда существует допустимое L, в противном случае вы бы указали, что делать, если нет.)

Попробуйте это онлайн!

Я не эксперт по вычислительной сложности, но идея перестраивать структуру данных каждый раз кажется плохой. Учитывая, что все хотят избежать копирования данных, я не думаю, что можно заново восстанавливать всё с нуля каждый раз.
Поэтому моя попытка заключается в том, чтобы постепенно строить две отсортированные последовательности (каждое вставление стоит log2 от числа уже вставленных элементов), а затем считывать их в порядке возрастания, чтобы получить количество элементов, которые в aArr больше различных элементов из bArr.

#include <iostream>
#include <span>
#include <set>

int minLenOfSubarrays(std::span<int> aArr, std::span<int> bArr, int M)
{
    std::set<int> a, b;
    for (int L = 0; L < int(aArr.size()); ++L) {
        a.insert(aArr[L]);
        b.insert(bArr[L]);
        auto it = begin(b);
        int count = 0;
        for (const auto& x : a) {
            if (x > *it) {
                ++it;
                ++count;
            }
        }
        if (count >= M) {
            return L + 1;
        }
    }
    return 0;
}

int main(int argc, char *argv[]) 
{
    {
        int aArr[] = { 2,4,10,6,1,11 };
        int bArr[] = { 3,5,8,9,7,12 };
        std::cout << minLenOfSubarrays(aArr, bArr, 3) << '\n';
    }
    {
        int aArr[] = { 2,4,10,6,1,11 };
        int bArr[] = { 3,5,8,1,9,7 };
        std::cout << minLenOfSubarrays(aArr, bArr, 4) << '\n';
    }
    {
        int aArr[] = { 2,4,10,6,1,11 };
        int bArr[] = { 3,5,8,1,9,12 };
        std::cout << minLenOfSubarrays(aArr, bArr, 6) << '\n';
    }
}

Я выбрал выводить 0, если мы не можем получить требуемое M, даже используя все массивы.

Множества обычно реализуются с помощью RB-деревьев, которые, как мне кажется, подходят для вашей задачи.

Вероятно, вам следует переключиться с int на size_t для возвращаемого значения, так как это число элементов. Что если у вас больше чем 2³¹-1 элементов? (StackOverflow определенно должен позволить использовать математическую разметку).

Примечание

Честно говоря, хотя я понимаю, как реализовать это с деревом, в котором каждый узел имеет два указателя на детей и дополнительный указатель на родителя, я не уверен, что смогу сделать это без указателя на родителя (для итерации по b). Должен ли я использовать стек? Можно ли это сделать с рекурсивными вызовами? Не имею понятия!