我在面试中遇到了以下问题,但找不到解决方法。
给定一个字符数组长度为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)时间复杂度内完成?
n
的数组,删除所有a
并复制所有b
而不使用额外空间?唯一关心的是“冗余段”中的a
和b
吗? - Patrick87[B,A,C,B,A,]
的答案是什么?而[B,C,A,B,A]
呢? - user58697