如何用两个字符替换数组中的特定字符

Question

所以我刚从工作面试回来，我不得不面对的问题之一是：

"给定一个字符数组和三个字符例如：

数组：[a,b,c,z,s,w,y,z,o]

字符 1：'z'

字符 2：'R' 字符 3：'R'

你的目标是在 O(N) 时间复杂度内将数组中的每个 'z' 替换为两个 R 字符。

因此您的输入将是数组：[a,b,c,z,s,w,y,z,o]

你的输出数组将是：[a,b,c,R,R,s,w,y,R,R,o]

假设之前的数组中没有'R'

不允许使用其他数组或其他变量。

算法应该是内联算法

您的最终数组必须是字符数组。"

我的解决方案是在 O(N^2) 时间复杂度内，但有一个解决方案在 O(N) 时间复杂度内。

面试结束了，我还在想这个问题，谁能帮我解决一下？

Answer 1

首先扫描输入以计算字符 1 出现的次数。这具有线性时间复杂度。

据此您知道最终数组的长度将是输入长度 + 出现次数。

然后将数组扩展到它的新长度，将新的槽留空（或任何值）。操作的确切性质取决于数组数据结构的实现方式。这肯定可以在最坏的线性时间复杂度下完成。

使用两个索引，i和j，其中i引用最后一个字符输入数组和 j 引用数组中的最后一个索引（可能指向一个空槽）。

开始从 i 复制到 j 每次将这些索引的值减一。如果复制匹配的字母，则将复制的字符再次复制到j，只减少j。这又具有线性时间复杂度。

算法将以 i 和 j 都等于 -1 结束。

Answer 2

进行两次迭代。

首先，计算 char1 的数量（在您的示例中为 'z'）。
现在你知道数组的末尾应该有多长了：array.size() + num_char1s

然后，使用输入和输出迭代器从最后到第一个。如果元素是 char1，则将新字符插入到末尾迭代器中，否则 - 只需复制。

伪代码：

num_char1s = 0
for x in array:
  if x == char1:
    num_char1s++

// Assuming array has sufficient memory already allocated.
out_iterator = num_char1s + size - 1
in_iterator = size - 1

while (in_iterator >= 0):
  if (array[in_iterator] == char1):
    array[out_iterator--] = char3
    array[out_iterator--] = char2
  else:
    array[out_iterator--] = array[in_iterator]
  in_iterator--

Answer 3

在你的问题中，有两点很重要。

不能使用新变量
不能使用新数组

所以，我们必须使用给定的数组。

首先我们将给定的数组大小增加一倍。为什么？因为最多我们的新数组大小 = given_array_size*2 (if all characters = char 1)
现在我们将向右移动给定数组 n 次，其中 n= given_array_size.
现在我们将从新的移位位置 = n 开始迭代我们的数组。 迭代 i=n 到 2*n-1
我们将取j=0，这将写入新数组。 如果我们找到 char 1，我们将使 array[j++]=char 2 和 array[j++]=char 3.
但是如果一个字符不是 'z'，我们就什么都不做。 数组[j++]=数组[i]
最后 0 到 j-1 是正确答案。

复杂度：O(n)
不需要新的变量和数组

如何用两个字符替换数组中的特定字符

How to replace a specific character in an array with two characters

arrays

string

algorithm

char