主页 / coding / 问题 / 79139213
Accepted
Mert
Asked: 2024-10-30 06:53:19 +0800 CST

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

  • 772

我需要找到大小为 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++

4 个回答

  1. Best Answer

    在二分搜索中，对每个搜索mid执行以下操作：

    1. 按升序计算 A[0:mid] 中的 M 个最大值。可以使用 AVL 树或大小为 M 的堆在 O(mid * logM) 内完成。这也是 O(N * logM)。
    2. 按升序计算 B[0:mid] 中的 M 个最小值。同样是 O(N * logM)。
    3. 并行检查它们，检查每个 A 值是否大于 B 值。耗时 O(M)，也是 O(N)。

    二分查找贡献了剩余的因子 logN。

    奖励：您可以在二分搜索之前对所有 A 值和所有 B 值进行排序，从而使其复杂度达到 O(N * logN)，然后对于每个值，mid您可以通过过滤那些已经排序的值来获得上述步骤 1 和 2 中的 A 值和 B 值。在“可执行伪代码”中：

    from bisect import bisect

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

# Sort indices by their values
N = len(A)
Ai = sorted(range(N), key=A.__getitem__)
Bi = sorted(range(N), key=B.__getitem__)

# Check whether A[:L] and B[:L] have the desired property 
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))

# Binary search, find the smallest L from M to N that's enough
L = bisect(range(N), False, M, N, key=enough)
print(L)

    （这假设总是存在一个有效的 L，否则您将指定如果没有 L 该怎么做。）

    在线尝试！

    我认为我们甚至可以实现 O(NlogM + MlogN)。仍然进行二分搜索，但不要为每个新的 都从头开始mid。而是只需更新M 个最大 A 值的树：

    • 如果mid大于之前的，则插入每个新值并在每次插入后删除最小值。B 类似。
    • 如果比之前小mid，则撤消您执行的插入/删除操作，以获得更大的。因此，这需要跟踪您执行的更新，至少要跟踪删除了哪些元素。插入了哪些元素是一目了然的。mid

    总体而言，您有 O(N) 个单值更新，每个更新的成本为 O(logM)。并且您有 O(logN) 个二分搜索轮次，每个轮次的成本为 O(M)，用于比较 M 对。（这可能受到Costantino 的回答的启发。）

    • 2 
  2. #include <iostream>
#include "AVLTree.h"
bool canSatisfy(int N, int M, int* aArr, int* bArr){
    AVLTree a;
    AVLTree b;

    for(int i = 0; i < N; i++){ // N*logM
        a.insertKey(aArr[i]);
        if(a.getSize() > M){
            a.removeKey(a.getMin());
        }
        b.insertKey(bArr[i]);
        if(b.getSize() > M){
            b.removeKey(b.getMax());
        }
    }
    int count = 0;
    while(a.getSize() != 0 && b.getSize() != 0){
        if(a.getMin() <= b.getMin()){
            return false;
        }
        a.removeKey(a.getMin());
        b.removeKey(b.getMin());
    }
    //total N*logM
    return true;
}
int main(int argc, char* argv[]){

    int aArr[] = {2,4,10,3,6,9,12,1,11,13,11,20};
    int bArr[] = {3,11,5,8,18,12,9,14,13,7,2,12};
    int N = 12;
    int M = 6;
    int L = 0;

    int left = M;
    int right = N;

    while(left <= right){ //Binary search logN
        int mid = left+((right-left)/2);
        if(canSatisfy(mid,M,aArr,bArr)){ // canSatisfy = N*logM
            L = mid;
            right = mid-1;
        }
        else{
            left = mid+1;
        }
    }
    //total O(N*logN*logM)
    std::cout << L << std::endl;
}

    我认为这个解决方案实现了所需的 O(N logN logM) 时间复杂度。感谢 @nocomment 的建议

    • 1

  3. 编辑：这比原来的提议更糟糕……叹息。

    我不是计算复杂性专家，但每次重建数据结构的想法让人感觉很糟糕。鉴于每个人都想避免复制数据，我认为每次都从头开始重建所有内容是不行的。所以我的尝试是逐步构建两个排序序列（每次插入的成本是已插入元素数量的 log2），然后按顺序读取它们，以计算 中aArr有多少元素大于 中的不同元素bArr。

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

int minLenOfSubarrays(std::span<int> aArr, std::span<int> bArr, int M)
{
    std::multiset<int> a{ begin(aArr), begin(aArr) + M - 1 };
    std::multiset<int> b{ begin(bArr), begin(bArr) + M - 1 };
    for (int L = M - 1; 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 绝对应该允许使用 KaTeX 标记）。

    附注

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

    • 0

  4. 当 L 比 N 小得多时，我还没有找到一种方法来在某种程度上不“蛮力”解决这一问题。

    1. 首先（在有帮助的情况下保持平衡）搜索树 X 和 Y，查找 A 和 B 中的前k = M 个元素。

    2. 检查完成：
      按顺序迭代 X 和 Y，将 X/A 元素与 Y/B 中对应的元素进行比较：当所有元素都较大时，以 L =  k终止。
      否则让 x 和 y 成为有问题的值。

    3. 处理下一对：

      1. 让 from1 = false 并将k增加一

      2. 让 X 表示 A 中前k 个元素中最大的 M 个元素：如果A 中的第 k个元素 r 不大于 X 中的最小元素，则 X 无需更改。否则，X 需要包含 r 并删除最小元素。
        如果 y < r，则 from1 = true

      3. 对称处理B 中的第k个元素（Y 是 M 个最小的元素）。

      4. 如果从1开始，则从1重复，否则从2开始。

    如果不能保证 L 存在，则需要在步骤 2 中首先处理该问题。
    可以修剪来自 A 的值恰好比来自 B 的值大一的对。强力
    步骤是步骤 1，不利用前面的检查。

    • 0

相关问题