给定N个排序数组,检查是否有两个包含至少两个公共元素的数组
YSh*_*hin 5 arrays sorting algorithm
如果你有N个排序数组,其中可能的元素是从0到N-1的整数,并且单个数组中的元素是不同的,那么如何检查是否至少有两个数组至少有两个元素是共同的？
例如,如果我有以下数组,其中N = 5:
A[0] = {0},
A[1] = {1, 3},
A[2] = {2},
A[3] = {1, 4},
A[4] = {1, 3}
然后A [1]和A [4]共有1和3,因此答案是正确的.
在N再次为5的其他示例中:
A[0] = {0, 4},
A[1] = {1, 3},
A[2] = {1, 2, 4},
A[3] = {0, 3},
A[4] = {1}
没有两个数组A [i],A [j]至少有两个共同的元素,因此答案是错误的.
这是一个采访问题的一部分,我只能在O(n ^ 3)时间内通过遍历每个数组组合(A [i],A [j])来解决,并且在每次迭代中我从0开始扫描到N-1来检查有两个共同的元素.
面试官表示有一个更快的解决方案,并暗示利用阵列的排序,但即使我在过去24小时内考虑这个问题,我也无法提出更好的解决方案.
什么是比O(N ^ 3)更快的算法来解决这个问题？谢谢.
