所以我刚面试回来，我不得不面对的一个问题是：
"给定一个字符数组和三个字符，例如：
阵列：[a，b，c，z，s，w，y，z，o]
字符1:'z'
字符2:'R'字符3:"R">
您的目标是将数组中的每个"z"替换为O(N(时间复杂性内的两个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(时间复杂性内，但有一个解决方案在0(N(时间复杂性范围内。
面试结束了，但我仍在思考这个问题，有人能帮我解决这个问题吗？
首先扫描输入，计算存在多少次char 1。这具有线性时间复杂性。
由此可知，最终数组的长度将是输入长度+出现次数。
然后将数组扩展到新的长度，使新插槽为空(或任何值(。操作的确切性质取决于数组数据结构的实现方式。在最坏的情况下，线性时间复杂性肯定可以做到这一点。
使用两个索引，i和j，其中i引用输入数组的最后一个字符，而j则引用数组中最后一个索引(可能指向空槽(。
开始从i复制到j，每次将这些索引的值减一。如果复制匹配的字母，则将复制的字符再次复制到j，并且只减少j。这再次具有线性时间复杂性。
该算法将以i和j均等于-1结束。
进行两次迭代。
首先，计算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--
在您的问题中，有两件事非常重要。
- 不能使用新变量
- 无法使用新数组
所以，我们必须使用给定的数组。
- 首先，我们将把给定的数组大小增加一倍。为什么？原因最多是我们的新数组大小=given_array_size*2(如果所有字符=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"，我们什么都不做array[j++]=array[i]
- 最后0到j-1是正确的答案
复杂性：O(n(
不需要新的变量和数组