时间戳

首页 > 解决方案 > 交错两个未排序的数组以获得词典最大的结果

algorithm - 交错两个未排序的数组以获得词典最大的结果

问题描述

假设我们有两个未排序的数组，A[1...m] 和 B[1...n]。目标是返回一个数组 C[1...(m+n)] 通过交织来自 A 和 B 的元素形成（换句话说，A[i] 必须在 A[i+1] 和 B[i] 之前必须在 C) 中的 B[i+1] 之前，以使 C 在字典顺序中尽可能大。有哪些方法可以在线性时间内解决这个问题？

基本方法是贪心的：如果 A[i] 大于 B[j]，则取 A[i] 并增加 i，否则如果 B[j] 大于 A[i]，则取 B[j] 并增加 j。当 A[i] 和 B[j] 相等时，就会出现困难。在这种情况下，我们必须“向前看”以找到第一个位置 k 使得 A[i+k] 和 B[j+k] 不同。C++ 中的代码如下所示：

// A, B are the input vectors
vector<int> C;
auto it1 = A.begin();
auto it2 = B.begin();
while (it1 != A.end() || it2 != B.end()) {
    if (std::lexicographical_compare(it1, A.end(), it2, B.end())) {
        C.push_back(*it2++);
    } else {
        C.push_back(*it1++);
    }
}

由于需要向前看，这可能需要二次时间。

在线性时间内执行此操作的一种方法是将两个数组与一个分隔符连接起来，该分隔符保证与原始数组的所有元素比较少，计算这个组合数组的后缀数组，并使用它以便轻松查找哪个suffix 更大，而不是在循环的每次迭代中进行完整扫描while。

标签： algorithm

解决方案

我只是要描述我在伪代码中拥有的部分算法。

首先是琐碎的案例。

if (it1 == A.end()) {
    copy from it2 until end
}
else if (it2 == A.end()) {
    copy from it1 until end
}
else if (*it1 < *it2) {
    copy one value from it1
}
else if (*it2 < *it1) {
    copy one value from it2
}
else {
    // This is where it gets tricky
    scan_forward(A, B, C, it1, it2)
}

现在的想法scan_forward是我们找到一种向前扫描的方法，然后获取一大块值。如果做得好，这应该花费很少的开销。但是“如果做得对”很棘手，我还没有完全弄清楚。想法还是这样。

it1_scan = copy of it1
it2_scan = copy of it2
while true {
    if (it1_scan == A.end()) {
        if (it2_scan == A.end() or  *it1 < *it2_scan) {
            copy it1 over
            copy it2 over
        }
        else if (*it1 == *it2_scan)  {
            scan forward on it2_scan
            if you find the end first or it2_scan finds something larger than *it1 {
                copy it1 over
                copy it2 over
            }
            else {
                copy it2 over until it2_scan's lower
                return and proceed
            }
        else {
            copy it2 until it2_scan
            return and proceed.
        }
    else if (it2_scan == B.end()) {
        Mirror logic for it2_scan knowing that it1_scan is not (yet) end.
    }
    else if (*it1_scan < *it2_scan) {
        copy it1 until it1_scan
        return and proceed.
    }
    else if (*it2_scan < *it1_scan) {
        copy it2 until it2_scan
        return and proceed.
    }
    else if (*it1 < *it1_scan) {
        copy it1 until it1_scan
        copy it2 until it2_scan
        return and proceed.
    }
    else {
       This is what I have not worked out.
       We want to do one of:
          - drain it1 and keep going
          - drain it2 and keep going
          - drain it1 then it2 then decide what to do.
    }

}

我开始写出复杂的部分，发现我有 3 门课程要并行学习。并且有很多选择。我没有详细解决这个问题，但似乎选项不会成倍增加。然而，你确实进入了一个奇怪的状态，你知道你想做一些事情，然后回溯并做其他一些事情。但是您还没有决定先复制哪个。这段逻辑可以持续很长时间，但我认为只有有限的开销。

但是，我承认没有详细说明那部分。

推荐阅读