访谈:列出有限内存的交集

Question

给定两组整数,大小为M和N,M <N.在这两组上执行内部相等连接(即,找到两个列表的交集).如果两个列表都在文件中且可用内存大小为K <M <N,则如何执行它

Answer 1

首先使用就地排序算法对两个列表进行排序。

一旦 M 和 N 都排序完毕，计算交集就像一场竞赛。将两个标记a和放置b在每个列表的开头。执行这些步骤，直到任何标记到达列表末尾。在伪代码中：

until a > M.size or b > N.size
    if M[a] < N[b]
        a++
        continue
    if N[b] < M[a]
        b++
        continue
    print M[a] // common element
    // Advance both indexes to avoid infinite loop
    a++
    b++

给定一个不错的就地排序算法，其复杂度将为O(nlogn)。