arrays - 如何组合三个数组的元素以获得想要的结果

Question

我在面试中被问到这个问题:

给定三个大小不等的数组和一个特定的数字，我必须从这三个数组中的每一个中选择一个数字，然后通过将 array1 和 array2 中的数字相除并将其与 array2 和 array3 中的数字相乘，找到是否可以获得特定号码？

For example: If I have three arrays: 
Array1: 4
Array2: 3 6
Array3: 2 3 8

而且我必须找到是否可以获得数字(1/4)？是的，可能是因为如果我从第一个数组中选择 4，从第二个数组中选择 6，然后从第二个数组中选择 3，从第三个数组中选择 8，我可以有，

(4/6)*(3/8) which makes it as 1/4. 

如何继续这个问题？为此，我想不出任何可靠的办法。谢谢!

Answer 1

让 M 成为您想要的数字。

您可以从 (array2,array3) 遍历所有对 (i,j)(其中有 O(n2*n3))，并存储值 array2[i ]/array3[j] 在一个集合中。

然后，遍历array1，array2中的所有对k,l(其中有O(n1*n2))，并检查是否有值在集合 x 中满足 array1[k]/array2[l] * x = M。
这可以通过简单地检查表中是否存在值 x = M*array2[l]/array1[k] 来完成。

假设集合的平衡树实现，这将花费 O(log(n2*n3) * (n1*n2 + n2*n3)) 时间。

通过选择存储最小化乘积总和的数组，可以对不等大小的数组进行一些改进:x1*x2 + x3*x4(其中 x1,x2,x3,x4)是数组的大小，array2“得到”这个等式中的两个变量)，所以你基本上可以有以下“存储”组合:

• array2/array3(如上例所示)
• array1/array2(并检查 x=M*array3/array2)
• array2/array2(并检查 x=M*array3/array1)
• array1/array3(并检查 x=M*array2/array2)
• array1*array2(并检查 x=M*array3*array2
• 1/(array2*array3)(并检查 x=M/(array2*array1)