在线排序和删除两个整数流上的重复项
Online sorting and removing duplicates on two streams of integers
假设我收到两个整数流。每个整数流 (1) 不保证按递增顺序排列，并且 (2) 有时，第一个流中会丢失一个或多个整数，但会出现在第二个流中。例如：
流 1 - 1, 2, 3, 5, 4, 6, 8, 9, 10, ...
流 2 - 1, 2, 3, 4, 5, 6, 8, 7, 10, ...
什么是数据结构 and/or 具有低 space 时间复杂度的算法，用于构建包含联合中 每个 单个整数的排序流（即删除重复项）两个流的集合？即：
排序流 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
当然，天真的方法是存储每个结果然后在 O(n log n) 中排序，最后通过线性扫描以删除所有连续的重复元素。但这需要大量内存，并且需要两个流在任何处理开始之前终止。
这是针对嵌入式设备上的 UDP 数据包定序器的，因此最好使用 C 语言的代码片段，但我也可以阅读 Python。
我们是否知道我们得到的整数，或者它们只是任意的？
您有时需要排序，所以我看不出有什么方法可以避免 O(n lg n)。最好的选择是 heapsort，它是为 sort-as-you-go 方法设计的。如果该值已经存在，则不要添加它。
（显然，不是排序，而是每次向堆中添加一个元素。）
假设我收到两个整数流。每个整数流 (1) 不保证按递增顺序排列，并且 (2) 有时，第一个流中会丢失一个或多个整数，但会出现在第二个流中。例如：
流 1 - 1, 2, 3, 5, 4, 6, 8, 9, 10, ...
流 2 - 1, 2, 3, 4, 5, 6, 8, 7, 10, ...
什么是数据结构 and/or 具有低 space 时间复杂度的算法，用于构建包含联合中 每个 单个整数的排序流（即删除重复项）两个流的集合？即：
排序流 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
当然，天真的方法是存储每个结果然后在 O(n log n) 中排序，最后通过线性扫描以删除所有连续的重复元素。但这需要大量内存，并且需要两个流在任何处理开始之前终止。
这是针对嵌入式设备上的 UDP 数据包定序器的，因此最好使用 C 语言的代码片段，但我也可以阅读 Python。
我们是否知道我们得到的整数，或者它们只是任意的？
您有时需要排序，所以我看不出有什么方法可以避免 O(n lg n)。最好的选择是 heapsort，它是为 sort-as-you-go 方法设计的。如果该值已经存在，则不要添加它。
（显然，不是排序，而是每次向堆中添加一个元素。）