algorithm - 算法/数据结构面试

Question

目标是将数组转换为a3b5c2就地aaabbbbbcc数组。我有一个解决方案：

• 假设数组是无限大的，
• 我从最后解析数组。
• 寻找一个数字（比如 n）
• 根据我得到的数字，我寻找下一个字符。
• 当我得到它时，我将元素从当前位置移动到数组末尾n-1。
• 用遇到的字符填充空缺职位。

该解决方案的复杂度为 O(n^2)。是否有复杂度小于 O(n^2) 的解决方案？

Answer 1

如果您解析一次数组，您可以通过对所有数值求和来知道最后一个元素的位置。

解析一次并找到它的最终大小。

一旦你这样做了，从“结束”开始填充它（从它的最终值开始）：2次c，然后5次b......

这是一个O(n)就地解决方案。

编辑：

正如 srbh.kmr 在评论中所说，如果数组中有一系列位置错误的字符仅重复一次，这将不起作用。例如，如果我们有数组a1b1c1d1e7，上面的答案将删除最后一个字母。

导致问题的唯一数字是1，我们可以将其处理为O(n)：

在按上述说明处理阵列之前，请消除这些阵列。从头开始，解析数组，每次1找到 a 时，擦除它并向前移动剩余的字母（不是整个剩余的数组，只是下一个字符）。如果在数组中找到几个1s，则数组的第一部分和第二部分之间的孔会变大。对于上面的示例数组，步骤如下所示：

a1b1c1d1e7
// First parse gives length = 1+1+1+1+7

// Repair ones
a b1c1d1e7
ab 1c1d1e7
ab  c1d1e7
abc  1d1e7
abc   d1e7
abcd   1e7
abcd    e7
abcde    7
abcde7

然后，应用上面的算法。如果在字符后没有找到数字，只需将字符复制到数组末尾的位置：

// Fill final array
abcde7    x
          ^ 11th position
abcde     e
abcde    ee
abcde   eee
abcde  eeee
abcde eeeee
abcdeeeeeee
abcdeeeeeee  // Here we overwrite the first "e"
abcdeeeeeee  // Then we see there are lone letters (4 times), so we leave them.