在没有额外空间的情况下改变阵列

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,插入额外的Bs

Answer 2

经过一些优化后，代码看起来像这样，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;
}