我在面试中被问到以下问题,但找不到解决方案。
给定一个长度为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) 时间复杂度内完成吗?
最佳答案
- 扫描数组以确定是否可以在可用空间中存储变异数组 -- 计算
A
和B
,并检查N-M >= numB- numA
- 从左到右遍历数组:将元素向左移动
A
的数量(填充 A 的位置) - 从右到左遍历数组:将元素向右移动
numB-B_so_far
,插入额外的B
关于arrays - 在没有额外空间的情况下改变数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43473035/