找到一个数组中只有两个数字，其中一个数字平均分割另一个数字 - 也就是说，除法运算的结果是整数
Input Arrays Output
5 9 2 8 8/2 = 4
9 4 7 3 9/3 = 3
3 8 6 5 6/3 = 2
具有嵌套循环的蛮力方法具有O(n^2)的时间复杂度。还有更好的方法，时间复杂度更低吗？
这个问题是advent of code的一部分。
我认为O(n^2)是您在没有任何数据假设的情况下获得的最佳时间复杂度。
如果你不能告诉任何有关这些数字的事情，知道x和y不会相互分开，不会告诉你关于任何x的z和y或z和x, y, z。因此，在最坏的情况下，你必须检查所有数字对 - 等于n Choose 2 = n*(n-1)/2 = O(n^2)。
显然，我们可以通过列出每个元素的除数对与数组中唯一值的散列来获得O(n * sqrt(m))，其中m是绝对值范围。根据输入，这可能比O(n^2)更有效。
5 9 2 8
list divisor pairs (at most sqrt m iterations per element m)
5 (1,5)
9 (1,9), (3,3)
2 (1,2)
8 (1,8), (2,4) BINGO!
给定一个数字A的数组，你可以通过将所有数字相乘得到E来识别分母，然后通过将E除以Ai2来测试每个第i个元素。如果这是一个整数，你就找到了分母，因为乘法不能引入其他因素。
一旦你有了分母，那么进行第二次独立循环搜索配对分子是一项简单的任务。
这消除了n2比较。
为什么这样做？首先，我们有一个n-2个非除数的集合：abcde ..为了完成数组，我们还有分子x和分母y。
但是，我们知道x和只有x的因子为y，所以它可以表示为yz（z是x除以y的整数余数）
当我们将所有数字相乘时，我们最终得到xyabcde ..，但是当x = yz时，我们也可以说y2zabcde ..
当我们循环除以数组中的平方第i个元素时，对于大多数元素，我们创建一个分数，例如为一个：
y2zabcde .. / a2 = y2zbcde .. / a
但是，仅适用于y和y：
y2zabcde .. / y ^ 2 = zabcde ..
为什么这不起作用？其他数字也是如此。不能保证a和b在乘法时不能产生另一个公因子。以[9,8,6,4]，9和8乘以等于72的例子为例，但由于它们都包括素数因子2和3,72因子也在数组中。当我们将它们全部乘以1728时，它们与原始的6相结合，这样它就可以完全划分为36。
怎么解决这个问题？更准确地说，如果y是x的因子，则y的素因子将唯一地成为x的素因子的子集，因此也许可以沿着这些线来细化。获得素数因子化不应该根据数组的大小进行缩放，但是比较子集会，所以我不清楚这是否有用。
如果你将数组中的所有数字逐步推入树中，当我们发现一个完全因子的数字叶子同时考虑另一个数字时，我们知道我们已经找到了除数。
但是，鉴于我们不知道哪个数是除数，我们确实需要测试所有素数，直到除数的最大因子。任何m位数的最大因子最多是sqrt（m），而任何m位数下的平均素数是m / ln（m）。这意味着我们将进行最多n（sqrt（m）/ ln（sqrt（m））运算，具有非常基本的因子分解和无优化。
更具体一点，该算法应该跟踪四个方面：探索的素因子的共同树，数组中的原始数，其当前的部分因子分解以及它在树中的位置。
对于每个素数，我们应该测试数组中的所有数字（反复考虑重复因子）。如果数字均匀分配，我们a）更新部分分解，b）添加/导航到树的相应子项，c）如果部分分解为1，我们找到了最后一个因子并且可以通过添加终止'1'孩子，和d）如果没有，我们可以检查留下孩子'1'的其他号码，以表明他们是完全分解的。
当我们找到一个孩子'1'时，我们可以通过将部分因子分解（例如树上的所有父母）和退出来识别另一个数字。
为了进一步优化，我们可以缓存数字的分解（部分和全部）。我们还可以停止检查具有独特因素的数字的其他因素，随着时间的推移缩小候选人的领域。