列表中的[j] = 2*A [i],其运行时间优于O(n ^ 2)

Question

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

给定整数数组A,检查是否存在两个索引i和j,使得A [j] = 2*A [i].例如,在数组(25,13,​​16,7,8)上,算法应该输出"true"(因为16 = 2*8),而在数组(25,17,44,24)上算法应该输出"假".描述这个问题的算法,最坏情况下的运行时间优于O(n ^ 2),其中n是A的长度.

谢谢!

Answer 1

这是使用哈希表的好地方.创建一个哈希表,并将数组中的每个数字输入哈希表.然后,再次遍历数组并检查每个i的哈希表中是否存在2*A [i].如果是这样,那么你知道这个属性存在一对索引.如果没有,你知道不存在这样的对.

在期望时,这需要时间O(n),因为对哈希表的n次操作采用预期的摊销O(1)时间.

希望这可以帮助!