找到最短子数组 A[0:L], B[0:L]，其中 A 中的 M 个不同元素大于 B 中的 M 个不同元素（时间复杂度）

Question

我需要找到大小为 L、A[0:L]、B[0:L] 的最小子数组，使得 A 中的 M 个不同元素大于 B 中的 M 个不同元素。就像 A[i] > B [j] 计数，但我不能再次使用 A[i] 或 B[j]。此外，子数组必须从数组的开头开始。

作业是关于 AVLTrees 和堆的，所以我想解决方案将涉及其中之一（对于下面的示例，我使用了 stl 中的priority_queue，但实际上我不允许使用任何库中的任何容器，所以我已经有了最小堆实现，但为了易于理解，我使用了等效的 stl）。我还希望使用 AVL 树或堆来解决这个问题。

诗。我发现数组可以包含重复的元素。

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; //min-heap
        //Heap b; //min-heap
        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)。

Answer 1

我不是计算复杂性专家，但每次都重建数据结构的想法感觉很糟糕。鉴于每个人都希望避免复制数据，我认为每次都从头开始重建一切是不可以的。 所以我的尝试是增量构建两个排序序列（每次插入都会花费已插入元素数量的 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 -1;
}

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';
    }
}

我还添加了一个

-1

，以防万一我们无法获得所需的

M

，即使使用所有数组也是如此。

集合通常使用 RB 树来实现，我认为这适合您的任务。

旁注

老实说，虽然我知道如何使用树来实现这一点，其中每个节点都有两个指向子节点的指针和一个指向父节点的附加指针，但我不确定如果没有指向父节点的指针我是否能够做到这一点（用于迭代 b)。我应该使用堆栈吗？这可以通过递归调用来完成吗？不知道！