java - 在常量空间中查找 k 个排序列表中的公共(public)元素(假设它们可以有重复值)

Question

我想知道找到 k 个排序的整数列表的交集的最有效解决方案是什么(假设它们可以有重复项)。我已经想出了一些解决方案。但我想知道是否有任何方法可以在恒定空间和最佳时间复杂度下做到这一点？

Ex:
for k=4
[[1,2,3,3,4],[2,3,3,5],[1,2,3,3,5,6,7],[1,2,3,3,6,7,8,9]]
should return [2,3,3]

Answer 1

这是一个通用算法，除了存储找到的公共(public)元素外不需要任何额外空间。

Place pointers at the start of each of the N arrays

Then repeat the following
    Check if all N elements are the same
    If yes, then
        Advance all N pointers by one
    If no, then
        Advance only the pointer of the smallest value
    Repeat this until all elements have been exhausted