列表中的A[j] = 2∗A[i]，优于O(n^2)运行时

Question

下面我列出了一个我遇到麻烦的问题。这个问题是一个简单的嵌套循环，远离O(n^2)解，但我需要它是O(n)。有什么办法解决这个问题吗？有可能形成两个方程吗？

给定整数数组A，检查是否有两个索引i和j，使Aj = 2∗Ai。例如，在数组(25，13，16，7，8)上，算法应该输出“true”(因为16 =2* 8)，而在数组(25，17，44，24)上，算法应该输出“false”。描述一个最坏情况下运行时间优于O(n^2)的问题的算法，其中n是A的长度。

谢谢!

Answer 1

这是一个很好的使用散列表的地方。创建一个哈希表，并在哈希表中输入数组中的每个数字。然后，再遍历数组一次，并检查每个i的哈希表中是否存在2*Ai。如果存在，那么您就会知道这个属性存在一对索引。如果没有，你知道不存在这样的一对。

对于期望，这需要时间O(n)，因为哈希表上的n个操作需要预期的摊销O(1)时间。

希望这能有所帮助！

Answer 2

使用散列表的建议是一个很好的建议。我想多解释一下为什么。

这里的关键是认识到，您实际上是在一组中搜索某个值。您有一组正在搜索的数字(输入数组中的每个值)，以及正在搜索的一组数字(输入数组中的每个值)。你的蛮力天真的例子就是直接在搜索数组中查找值。您想要做的是预加载您的“搜索-in”设置为比数组更快的查找(如哈希表)，然后您可以从那里进行搜索。

您还可以通过不搜索A[i] ( A[i]是奇数)来进一步修剪您的结果；因为您知道，如果A[i]是奇数，A[i] = 2 * A[j]永远不会是真的。您还可以在初始化期间动态计算"search- in“数组中的最小值和最大值，并在该范围之外修剪所有A[i]。

那里的性能很难用大O格式表示，因为它取决于数据的性质，但您也可以计算最佳和最坏情况以及摊销情况。

但是，如果正确选择哈希表大小(如果您的值范围很小，您只需选择比值范围更大的容量，而哈希函数本身就是值)，在某些情况下，剪枝的成本实际上可能会更高，您必须对其进行分析才能找到答案。