三个阵列中如何结合的元素，以获得想要的结果

不同尺寸和特定的一些考虑三个阵列，我必须从每三个中选择一个号码数组，并通过将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，I可以具有

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

如何使用这个问题继续？我无法为此提供任何有用的信息。谢谢！

2015-09-20 rohansingh

所有输入的范围是什么？ –

我想到的一种方法是O（n^3），但它会超过时间限制，因为单个值可能高达10^9。 – rohansingh

@rohansingh，你有时间，空间的限制吗？ –

让M成为您想要的数字。

你可以从（array2，array3）（其中有O（n2 * n3）那些）的所有对(i,j)，并将值array2[i]/array3[j]存储在一个集合中。

然后，遍历所有对k,l中ARRAY1，数组2（还有那些的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“获取”两个变量这个方程），这样就可以基本上具有以下 “存储” 的组合：

2015-09-20 05:59:40 amit

我不确定，但不能得到为什么你从第三阵列中存储分割对？它不是来自array2除以array3的对吗？你会得到O（n1 * n2 + n2 * n3）？ –

@GiorgiNakeuri我正在做这个“诡计”，以获得更好的复杂性（二次方代替立方）。我存储所有对，并检查配对。这仍然保证检查所有可能性，并降低复杂性。 – amit

我的意思是不应该这个'array3 [i]/array3 [j]'是这个'array2 [i]/array3 [j]'？ –

您可以消除考生和通过观察倍数，而不是商降低最坏情况下的时间复杂度O(n2 * n3 + n1 * n2)：

首先，哈希只有那些倍数，a2 * a3; a2 ∈ array2, a3 ∈ array3，均匀地将对象分割分母。在你的例子中，这些将是，{3 * 8/4 = 6, 6 * 2/4 = 3, 6 * 8/4 = 12}。

然后，在哈希表中寻找一个倍数a1 * a2/target numerator; a1 ∈ array1, a2 ∈ array2。在你的例子中，那将是4 * 3/1。

（反向为整数指标，从array1和array2元件由目标均匀划分的第一散列倍数的过程中，则匹配从array2和array3元件的倍数。）

假设平均复杂度为哈希表（ O(n)构造，O(1)查找），总体最坏情况时间复杂度应该是O(n2 * n3 + n1 * n2)。对于大输入基数，排序后的哈希表和数组可以允许早期检测到没有解决方案。

2015-09-20 16:55:17

回答