在没有额外 space 的情况下改变数组

Question

我在面试中被问到以下问题，但找不到解决方案。

给定的是一个字符数组，长度为n，并且"important section"（必须保存该部分的所有字符）长度m 其中 n >= m >= 0 如下：

没有多余的space，执行以下过程：
删除所有出现的 A 并复制所有出现的 B，return 变异数组的子数组。例如，对于上面的数组 [C,A,X,B,B,F,Q] n=7, m=5 ，输出将是 [C,X,B,B,B,B]。请注意，变异的数组长度为 6，因为 Q 在冗余部分并且 B 被重复。

Return -1 如果无法执行操作。

示例：

n=2, m=2 , [A,B] => [B,B]  
n=2, m=2 , [B,B] => -1 (since the result [B,B,B,B] is larger then the array)  
n=3, m=2 , [A,B,C] => [B,B]  
n=3, m=3 , [A,B,C] => [B,B,C]  
n=3, m=2 , [Z,B,A] => [Z,B,B] (since A was in the redundant section)

寻找代码示例，这可以在 O(n) 时间复杂度内完成吗？

Answer 1

扫描数组以确定是否可以在可用的 space 中存储变异数组 -- 计数 As 和 B，并检查 N-M >= numB-numA
从左到右遍历数组：将元素向左移动 A 的数量（填充 A 的位置）
从右到左遍历数组：将元素向右移动 numB-B_so_far，插入额外的 Bs

Answer 2

从输入数组的末尾开始。我们会从后往前弄清楚要填什么。

查看输入中的最后一个重要字符（位置 m）。如果是a，忽略它。否则，添加符号。重复直到读完所有输入。

这会删除 as。现在我们将复制 bs.

从数组的开头开始。找到您在上述步骤中写入的最后一个值。如果是b，写两个b。如果是别的，就写其中一个。重复。注意：如果你 "catch up"，需要在你需要阅读的地方写，你没有足够的空间，你输出 -1。否则，return数组从位置1到最后读取位置的部分。

示例：

Phase 1: removing A
CAXBBFQ
CAXBBFB
CAXBBBB
CAXBXBB
CAXCXBB

Phase 2: duplicating B
CAXCXBB
CXXCXBB
CXBBXBB
CXBBBBB
^^^^^^

第 1 阶段是线性的（我们读取 m 个符号并写入不超过 m 个）。

第 2 阶段是线性的（我们读取的符号少于 m 个，写入的符号不超过 2m 个）。

m 小于 n 所以一切都是 O(m) 和 O(n).

Answer 3

经过一些优化的代码看起来像这样，O(n):

// returns length of the relevant part of the mutated array or -1
public static int mutate(char[] a, int m) {
    // delete As and count Bs in the relevant part
    int bCount = 0, position = 0;
    for (int i = 0; i < m; i++) {
        if (a[i] != 'A') {
            if (a[i] == 'B')
                bCount++;
            a[position++] = a[i];
        }
    }
    // check if it is possible
    int n = bCount + position;
    if (n > a.length)
        return -1;
    // duplicate the Bs in the relevant part
    for (int i = position - 1, index = n - 1; i >= 0; i--) {
        if (a[i] != 'B') {
            a[index--] = a[i];
        } else {
            a[index--] = 'B';
            a[index--] = 'B';
        }
    }
    return n;
}

在没有额外 space 的情况下改变数组

Mutating an array without extra space

arrays

algorithm

time-complexity

space-complexity