是的,这可以在 O( n ) 时间内就地完成,假设两个输入都已排序,并且一次通过两个向量。就是这样:
扩展A
(目标向量)B.size()
- 为我们的新元素腾出空间。
向后迭代两个向量,从 的末尾B
和 的原始末尾开始A
。如果向量按小→大排序(最后大),则取指向较大数字的迭代器,并将其粘贴在A
. 继续直到B
的迭代器到达B
. 反向迭代器在这里应该特别好。
例子:
A: [ 1, 2, 4, 9 ]
B: [ 3, 7, 11 ]
* = iterator, ^ = where we're inserting, _ = unitialized
A: [ 1, 3, 4, 9*, _, _, _^ ] B: [ 3, 7, 11* ]
A: [ 1, 3, 4, 9*, _, _^, 11 ] B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9, _^, 9, 11 ] B: [ 3, 7*, 11 ]
A: [ 1, 3, 4*, 9^, 7, 9, 11 ] B: [ 3*, 7, 11 ]
A: [ 1, 3*, 4^, 4, 7, 9, 11 ] B: [ 3*, 7, 11 ]
A: [ 1, 3*^, 3, 4, 7, 9, 11 ] B: [ 3, 7, 11 ]
超级编辑:你考虑过std::inplace_merge
吗?(我可能刚刚重新发明了它?)