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

Question

假设我们有两个未排序的数组，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++);
    }
}

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

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

• 由于后缀数组构造相对复杂，我很想知道是否存在更简单的方法。
• 此外，后缀数组使用线性额外内存，我想知道是否有一种解决方案需要线性时间并且只使用常量额外内存。 (我的意思是输出数组 C 占用的内存不计入限制，但你只能追加到 C，此后不能返回读取或写入 C 的任何先前元素。)

Answer 1

我将用伪代码描述部分算法。

首先是琐碎的情况。

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 门类(class)要同时学习。还有很多选择。我没有详细解决这个问题，但似乎选项并没有成倍增加。然而，你确实会进入一种奇怪的状态，你知道你想做其中的一些，然后原路返回并做其他的一些。但是您还没有决定先复制哪个。这段逻辑可以持续很长时间，但我认为只有有限的开销。

不过，我承认我没有详细说明这部分内容。