为了找到 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;
我可以应用什么优化来加快速度?有没有更快的方法?
编辑:数组中的数据未排序。
最佳答案
有一种更快的方法:列表比较算法。它允许您以线性时间而不是二次时间比较两个列表。基本思想如下:
- 按相同条件对两个列表进行排序。 (如果您需要保留原始顺序,请先复制列表。)
- 从两个列表的顶部开始。从每个项目中选择第一项并进行比较。
- 如果它们匹配,则处理该情况并提升两个列表的索引。
- 如果不匹配,则循环遍历,每次都使用“较小”值推进列表的索引,直到找到匹配项。
- 当您到达任一列表的末尾时,您就完成了。 (除非您想处理其他列表中的剩余内容。)
这可以扩展到处理 2 个以上的列表,只需付出一些努力。
关于arrays - Delphi中N数组的交集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9038618/