主页 / user-24980196

Mert's questions

Martin Hope
Mert
Asked: 2024-10-30 06:53:19 +0800 CST
  • 8

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

作业是关于 AVLTrees 和 Heap 的，所以我猜解决方案会涉及其中之一（对于下面的示例，我使用了 stl 中的 priority_queue，但实际上我不允许使用任何库中的任何容器，所以我已经有了 min-heap 实现，但为了易于理解，我使用了 stl 等效项）。此外，我还希望使用 AVL Tree 或 Heap 来解决问题。

附言：我发现数组可以包含重复元素。

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)。

c++