arrays - 在没有额外空间的情况下改变数组

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) 时间复杂度内完成吗？

Answer 1

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