问题

给定一个数组,从数组的开始到它的结束,每当遇到数字“2”时,就在数组之后添加另一个“2”。
2001年12月31日终了的两年期收入和支出及准备金和基金结余变动报表 在这样做时,将删除数组中的最后一个元素,因为最终数组的大小应该与初始数组相同。

例如,如果初始数组是

 [23, 2, 3, 12, 2, 2, 34, 55, 66, 79]
 

那么修改后的数组应该是

 [23, 2, 2, 3, 12, 2, 2, 2, 2, 34]
 

预期的时间复杂性是 O(n),您应该做到这一点(只使用常量的额外内存)。

在O(n^2)中很容易,但在O(n)中???

  最佳答案

使两个通过数组

  1. 迭代计算你发现的2s,并跟踪最终数组的大小,以便你知道什么时候停止.在你的例子中,当你到达34时,你应该知道最后三个元素并不重要,因为你之前已经看到了3个2s.记住你停止的位置.
  2. 向后遍历第一个传递中停止的数组.将每个元素复制到数组的末尾.如果是2,则复制两次.

有一个角落的情况可以处理最后一个符合的元素是2,但没有其副本的空间.你必须在这两个传递中都说明这一点.

  相同标签的其他问题

algorithmcomplexity-theory