arrays - Delphi中N数组的交集

Question

为了找到 N 个数组的交集，我有这个实现，但效率非常低。我知道必须有一种算法来加快速度。

注意:myarray 是包含我想要查找其交集的所有其他数组的数组。

var
i, j, k: integer;
myarray: Array of Array of integer;
intersection: array of integer;

for I := 0 to length(myarray)-1 do
  begin
    for J := 0 to length(myarray)-1 do
    begin
      if i = j then
        continue;
      for k := 0 to length(myarray[i])-1 do
      begin
        if myarray[i][j] = myarray[j][k] then
        begin
          setLength(intersection, length(intersection)+1);
          intersection[length(intersection)-1] := myarray[j][k];
        end;
      end;
    end;
  end;

我可以应用什么优化来加快速度？有没有更快的方法？

编辑:数组中的数据未排序。

Answer 1

有一种更快的方法:列表比较算法。它允许您以线性时间而不是二次时间比较两个列表。基本思想如下:

1. 按相同条件对两个列表进行排序。 (如果您需要保留原始顺序，请先复制列表。)
2. 从两个列表的顶部开始。从每个项目中选择第一项并进行比较。
3. 如果它们匹配，则处理该情况并提升两个列表的索引。
4. 如果不匹配，则循环遍历，每次都使用“较小”值推进列表的索引，直到找到匹配项。
5. 当您到达任一列表的末尾时，您就完成了。 (除非您想处理其他列表中的剩余内容。)

这可以扩展到处理 2 个以上的列表，只需付出一些努力。