c++ - 以有限的界限有效地合并两个列表

Question

我正在尝试合并两个数组/列表，其中必须比较数组的每个元素。如果它们中有一个相同的元素，我将它们的总出现次数增加一个。数组都是二维的，其中每个元素都有一个计数器来记录它的出现。我知道这两个数组都可以与 O(n^2) 中的双循环进行比较，但是我受到 O(nlogn) 的限制。如果出现不止一次，最终数组将包含两个列表中的所有元素及其增加的计数器

Array A[][] = [[8,1],[5,1]]
Array B[][] = [[2,1],[8,1]]

合并完成后我应该得到一个这样的数组

Array C[][] = [[2,1],[8,2],[8,2],[5,1]]

元素的排列不是必须的。

根据阅读资料，Mergesort 需要 O(nlogn) 来合并两个列表，但是我目前遇到了我的绑定(bind)问题的障碍。任何伪代码可视化将不胜感激。

Answer 1

我很喜欢Stepanov's Efficient Programming尽管它们相当慢。在第 6 节和第 7 节中(如果我没记错的话)，他讨论了算法 add_to_counter() 和 reduce_counter()。当然，这两种算法都非常简单，但可以毫不费力地用于实现非递归归并排序。唯一可能不明显的见解是组合操作可以将两个元素缩减为一个序列，而不仅仅是一个元素。要就地执行操作，您实际上需要使用合适的类来存储迭代器(即数组中的指针)来表示数组的部分 View 。

我还没有看过第 7 节之后的类(class)(实际上什至还没有看过完整的第 7 节)，但我完全希望他能真正展示如何使用第 7 节中产生的计数器实现，例如，合并排序。当然，归并排序的运行时复杂度是 O(n ln n) 并且，当使用计数器方法时，它将使用 O(ln n) 辅助空间.