假设我收到两个整数流。每个整数流 (1) 不保证按递增顺序排列，并且 (2) 有时，第一个流中会丢失 1 个或多个整数，但会出现在第二个流中。例如:
流 1 - 1、2、3、5、4、6、8、9、10、...
流 2 - 1、2、3、4、5、6、8、7、10、...
什么是具有低时空复杂度的数据结构和/或算法来构建包含两个流的并集(即删除重复项)中的每个单个整数的排序流？即:
排序流 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
当然，最简单的方法是存储每个结果，然后以 O(n log n) 的时间排序，在线性扫描中进行最后一次删除所有连续的重复元素。但这需要大量内存，并且需要两个流在任何处理开始之前终止。
这是针对嵌入式设备上的 UDP 数据包定序器，因此最好使用 C 语言的代码片段，但我也可以阅读 Python。
最佳答案
我们是否知道我们得到的整数，或者它们只是任意的？
你需要在某个时刻进行排序，所以我没有找到避免 O(n lg n) 的方法。你最好的选择是 heapsort它是为“按需排序”方法而设计的。如果该值已经存在，则不要添加它。
(显然，您每次都会向堆中添加一个元素，而不是排序。)
关于python - 在线排序并删除两个整数流上的重复项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34822791/