Interview:列出内存有限的交叉点

Question

给定两组整数，大小分别为M和N，其中M

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

Answer 2

1. 将N拆分为n个部分L (L
2. 一次读取M个数字，将该数字与当前部分L
3. 中的所有数字进行比较，如果找到匹配，则将其写入文件

Answer 3

取M的K/2元和N的K/2元，排序M-子集和N-子集。现在，交集是微不足道的。写交集，删除交集的元素，写回左边的元素。继续使用M和N的所有其他K/2子部分。现在，在第三个文件中有一些公共元素，以及一些部分排序的列表。现在，对于M和N列表的每个K/2(减去删除的元素)，比较它们以有效地找到交集。

(您还可以添加2个M子集和N子集的额外轮次合并，以加快相交速度)。

太棒了！

执行示例：

Ok let's take 2 lists of 9 integers with values between 0 and 9.
These lists will be
4 2 5 1 9 2 9 0 2
and
4 7 4 0 8 6 2 6 5
(generated by rand())

So we take two sublists : 
4 2 5 and 4 7 4

Let's sort them using quicksort
4 2 5
i   j <- two pointers
pivot = [0] = 4

increase i until it's greater than pivot = 4
i and j now points to 5
decrease j until it's smaller than pivot = 4
j points to 2
i is greater than j, thus except for pivot, the list is sorted.
Swap [0] and [j] to finish sorting
2 4 5.

Except for pivot + i + j, no extra allocation was needed (For 3 elements it's hard to believe, see any quicksort applet to have a better understanding).
Thus, from an algorithmic point of view, pivot + i + j are constant and can be neglected (in fact you would do memory - algorithm size to have the real K).

Do the same for the second set
(4 4 7)

Now with two pointers to the lists initialized to the start of the sublists, compare the pointed values.
2 - 4
Increase first sublist's pointers
4 - 4
Equal -> a first common element, remove them from list [2 5] and [4 7]
5 - 4
Increase second pointer
5 - 7
Increase first pointer
End of this sublists.

Dump this to original lists.
Do this for any other sublists
[1 9 2] and [0 8 6] -> [1 2 9] [0 6 8] -> no intersection
[9 0 2] and [2 6 5] -> [0 9 E] [5 6 E] -> [2]

Now we have : 
[2 5 E 1 2 9 0 9 E] and [4 7 E 0 6 8 5 6 E] with E for empty elements.
Now compare subsets with other subsets (sorted) (excepted for already processed sets (same index))
[2 5 E] with [0 6 8] and [6 5 E] -> becomes [2 E E] and [0 6 8] [6 E E]  (intersection [5])
Then
[1 2 9] with [4 7 E] and [6 E E] -> [1 2 9] and [4 7 E] [6 E E] (no intersection)
Then
[0 9 E] with [4 7 E] and [0 6 8] -> [9 E E] and [4 7 E] [6 8 E] (intersection [0])
End : 
[2 E E 1 2 9 9 E E] [4 7 E 6 8 E 6 E E] with common elements [4 2 5 0]