If you have N sorted arrays where possible elements are integers from 0~N-1, and elements in a single array are distinct, how do you check if there are at least two arrays such that at least two elements are common?
如果你有N个排序数组,其中可能的元素是从0到N-1的整数,并且单个数组中的元素是不同的,那么如何检查是否至少有两个数组至少有两个元素是共同的?
For example, if I have following arrays where N = 5:
例如,如果我有以下数组,其中N = 5:
A[0] = {0},
A[1] = {1, 3},
A[2] = {2},
A[3] = {1, 4},
A[4] = {1, 3}
then A[1] and A[4] both have 1 and 3 in common, and therefore the answer is true.
然后A [1]和A [4]共有1和3,因此答案是正确的。
In other example where N is again 5:
在N再次为5的其他示例中:
A[0] = {0, 4},
A[1] = {1, 3},
A[2] = {1, 2, 4},
A[3] = {0, 3},
A[4] = {1}
No two arrays A[i], A[j] have at least two elements in common, therefore the answer is false.
没有两个数组A [i],A [j]至少有两个共同的元素,因此答案是错误的。
It was part of an interview question, which I was only able to solve in O(n^3) time, by iterating through each combination of arrays(A[i], A[j]) and in each iteration I scan from 0 to N-1 to check there are two common elements.
这是一个面试问题的一部分,我只能在O(n ^ 3)时间内通过遍历每个数组组合(A [i],A [j])来解决,并且在每次迭代中我从0开始扫描到N-1来检查有两个共同的元素。
The interviewer indicated that there is a faster solution, and kind of hinted that utilize sortedness of the arrays, but I wasn't able to come up with better solution even if I was thinking of this problem for last 24 hours.
面试官表示有一个更快的解决方案,并暗示利用阵列的排序,但即使我在过去24小时内考虑这个问题,我也无法提出更好的解决方案。
What would be a faster algorithm than O(N^3) to solve this problem? Thank you.
什么是比O(N ^ 3)更快的算法来解决这个问题?谢谢。
2 个解决方案
#1
6
Create graph with array vertices and number vertices (at most 2N vertices).
Connect every array vertice with its numbers.
If two arrays have a pair of common numbers, there is cycle with length=4 (B-1-C-2 at the picture)
使用数组顶点和数字顶点(最多2N个顶点)创建图形。将每个数组顶点与其数字相连。如果两个数组有一对公共数字,则存在长度= 4的周期(图中的B-1-C-2)
Find if such cycle exists
Both creating graph and searching cycle takes O(N^2)
查找是否存在这样的循环创建图形和搜索循环都需要O(N ^ 2)
#2
1
It's doable in O(n*m) with n = number of elements and m = number of arrays
它在O(n * m)中是可行的,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
The algorithm iterates over all arrays "at once" always continuing with the smallest element. This element is compared to the smallest not visited elements of the other arrays. If the element are equal a not is taken in the commons array to keep track of the number of common elements.
该算法“一次”迭代所有数组,始终以最小元素继续。将此元素与其他数组中最小的未访问元素进行比较。如果元素相等,则在公共数组中采用not来跟踪公共元素的数量。
After every element was visited, you only have to look into the common matrix to see which arrays have more than two common elements.
在访问每个元素之后,您只需要查看公共矩阵以查看哪些数组具有两个以上的公共元素。
EDIT: over read something in the question. Sorry
编辑:过度阅读问题中的内容。抱歉
#1
6
Create graph with array vertices and number vertices (at most 2N vertices).
Connect every array vertice with its numbers.
If two arrays have a pair of common numbers, there is cycle with length=4 (B-1-C-2 at the picture)
使用数组顶点和数字顶点(最多2N个顶点)创建图形。将每个数组顶点与其数字相连。如果两个数组有一对公共数字,则存在长度= 4的周期(图中的B-1-C-2)
Find if such cycle exists
Both creating graph and searching cycle takes O(N^2)
查找是否存在这样的循环创建图形和搜索循环都需要O(N ^ 2)
#2
1
It's doable in O(n*m) with n = number of elements and m = number of arrays
它在O(n * m)中是可行的,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
The algorithm iterates over all arrays "at once" always continuing with the smallest element. This element is compared to the smallest not visited elements of the other arrays. If the element are equal a not is taken in the commons array to keep track of the number of common elements.
该算法“一次”迭代所有数组,始终以最小元素继续。将此元素与其他数组中最小的未访问元素进行比较。如果元素相等,则在公共数组中采用not来跟踪公共元素的数量。
After every element was visited, you only have to look into the common matrix to see which arrays have more than two common elements.
在访问每个元素之后,您只需要查看公共矩阵以查看哪些数组具有两个以上的公共元素。
EDIT: over read something in the question. Sorry
编辑:过度阅读问题中的内容。抱歉