不使用额外空间改变数组

Question

我在面试中遇到了以下问题，但找不到解决方法。

给定一个字符数组长度为n，并且有一个“重要部分”（该部分中的所有字符必须被保存）长度为m，其中n≥m≥0，如下所示：

不使用额外空间，执行以下过程：
删除所有出现的A，复制所有出现的B，返回变异后的子数组。例如，对于上述数组[C,A,X,B,B,F,Q]，n=7，m=5，输出将是[C,X,B,B,B,B]。请注意，变异后的数组长度为6，因为Q在冗余部分中，而B被复制了。

如果无法执行操作，请返回-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)时间复杂度内完成？

- Roni Gadot

---

所给定的数组是否像你所说的“删除所有 A 的出现”一样是“动态”的？ - tourist

“m”的意义是什么？为什么不直接问，给定长度为n的数组，删除所有a并复制所有b而不使用额外空间？唯一关心的是“冗余段”中的a和b吗？ - Patrick87

m 是必须保留的字符长度，m 后面的任何空格都可以用于操作。 - Roni Gadot

[B,A,C,B,A,]的答案是什么？而[B,C,A,B,A]呢？ - user58697

Answer 1

1. 扫描数组以确定是否可以将变异后的数组存储在可用空间中 - 统计A和B的数量，并检查N-M>=numB-numA
2. 从左到右遍历数组：将元素向左移动已经存在的A数量（填充A的位置）
3. 从右到左遍历数组：将元素向右移动numB-B_so_far次，插入额外的B。

- MBo

---

解决方案的时间复杂度是多少？ - Roni Gadot

你可以在回复中添加一些代码，这样我就可以接受它了吗？ - Roni Gadot

它的时间复杂度为O(3n) = O(n)。但是你可以少做一次迭代。第一次传递数组时，删除A并仅计算B的数量，然后决定是否可能并继续进行第三步。 - maraca

@Roni Gadot 我相信每个人都可以实现这样的算法并获得有价值的想法；-)（注意-这是SO的算法部分）。看看来自maraca的优化版本（步骤1和2在单次运行中）。 - MBo

我同意，想法是最重要的，否则你不能编程。但仅仅用可理解的步骤表达解决方案不仅是一种艺术形式，将语言翻译成代码也是如此。有无数种方法可以做到这一点，有些比其他方法更优雅，特别是对于初学者来说，这可能相当困难。 - maraca

@maraca 我本来希望那位作者能够尝试编写部分代码，至少是第一步（请注意-这个问题是来自面试）。是的，他/她可以从你精美的代码中学习。 - MBo

Answer 2

从输入数组的末尾开始。我们将从后往前确定要填充什么。

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

这将删除a。现在我们将复制b。

从数组开头开始。找到上述步骤中最后写入的值。如果它是b，则写入两个b。如果是其他内容，请只写入其中一个。重复此操作。注意：如果您“赶上了”，需要在需要读取的位置写入，则没有足够的空间，您将输出-1。否则，返回从位置1到最后读取的位置的数组部分。

例子：

Phase 1: removing A
CAXBBFQ
CAXBBFB
CAXBBBB
CAXBXBB
CAXCXBB

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

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

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

m小于n，因此所有内容都是O(m)和O(n)。

- Patrick87

---

你能否在回复中添加一些代码，以便我可以接受它？ - Roni Gadot

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;
}

- maraca