给定N个排序数组，检查是否有至少包含两个公共元素的两个数组

Question

如果有N个排序数组，其中可能的元素是0~N1的整数，并且单个数组中的元素是不同的，那么如何检查是否至少有两个数组这样至少两个元素是公共的？

例如，如果我有以下数组，其中N= 5：

A[0] = {0},
A[1] = {1, 3},
A[2] = {2},
A[3] = {1, 4},
A[4] = {1, 3}

然后A1和A4都有1和3的共同点，因此答案是正确的。

在另一个例子中，N又是5：

A[0] = {0, 4},
A[1] = {1, 3},
A[2] = {1, 2, 4},
A[3] = {0, 3},
A[4] = {1}

没有两个数组Ai，Aj至少有两个共同的元素，因此答案是假的。

这是面试问题的一部分，我只能在O(n^3)时间内，通过遍历数组(Ai，Aj)的每个组合，在每一次迭代中，从0扫描到N-1来检查有两个共同的元素。

面试官指出，有一个更快的解决方案，并暗示利用数组的排序，但我无法想出更好的解决方案，即使我考虑了这个问题过去24小时。

有什么比O(N^3)更快的算法来解决这个问题？谢谢。

Answer 1

创建具有数组顶点和多个顶点的图(最多为2N个顶点)。

将每个数组顶点与其编号连接起来。

如果两个数组有一对公共数字，则有length=4循环(图中为B-1-C-2)。

​

​

寻找if such cycle exists

创建图和搜索周期都需要O(N^2)。

Answer 2

它可以在n = number of elements和m = number of arrays的O(n*m)中实现。

pointers[m] // one pointer for every array starting at begin();
commons[m][m] = 0 // count commons for every array combination
while(any pointer != end() )
{
   find pointer with lowest value;
   if any other pointer has this value;
      common[x][y] ++; // increment the commons counter for the corresponding arrays
   increment chosen pointer;
}
where common[x][y] >= 2 -> arrays contain 2 or more common elements

该算法“一次”遍历所有数组，总是以最小的元素继续。将此元素与其他数组的最小未访问的元素进行比较。如果元素等于a，则在commons数组中取not，以跟踪公共元素的数量。

在访问每个元素之后，您只需查看common矩阵，就可以查看哪些数组有两个以上的公共元素。

编辑:过度阅读问题中的某些内容。抱歉的