algorithm - 采访 : lists intersection with limited memory

Question

给你两组整数，大小为 M 和 N，其中 M < N。对这两组进行内部相等连接(即找到两个列表的交集)。如果两个列表都在文件中并且可用内存大小为 K < M < N

如何执行它

Answer 1

使用 in-place sorting algorithm首先对两个列表进行排序。

一旦 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)。