algorithm - 检查未排序数组 a 中是否存在 a[i] = 2*a[j]？

Question

给定一个未排序的整数序列 a[1,...,n]，给出一个 O(nlogn) 运行时算法来检查是否有两个索引 i 和 j 使得 a[i] =2*a[j ].该算法应在输入 4、12、8、10 上返回 i=0 和 j=2，在输入 4、3、1、11 上返回 false。

我认为无论如何我们都必须对数组进行排序，时间复杂度为 O(nlogn)。我不确定在那之后该怎么做。

Answer 1

注意:平均可以在 O(n)¹ 上完成，使用 hash table .

set <- new hash set
for each x in array:
   set.add(2*x)
for each x in array:
   if set.contains(x): 
        return true
return false

证明:
=>
如果有 2 个元素 a[i] 和 a[j] 使得 a[i] = 2 * a[j]，然后在第一次迭代时，我们在读取a[j]时将2*a[j]插入集合。在第二次迭代中，我们发现 a[i] == 2* a[j] 在集合中，并返回 true。

<=
如果算法返回真，则它发现 a[i] 使得 a[i] 已经在第二次迭代的集合中。因此，在第一次迭代期间 - 我们插入了 a[i]。这只有在存在第二个元素 a[j] 使得 a[i] == 2 * a[j] 时才能完成，我们插入了 a[i] 在阅读 a[j] 时。

注意:
为了返回元素的索引，可以简单地使用 HashMap 而不是集合，并且对于每个i存储2 *a[i] 作为键，i 作为值。

示例:
输入 = [4,12,8,10]

首先对每个x - 2x插入到哈希表中，并进行索引。你会得到:

哈希表 = {(8,0),(24,1),(16,2),(20,3)}

现在，在第二次迭代中，您检查每个元素是否在表中:

arr[0]: 4 is not in the table
arr[1]: 12 is not in the table
arr[2]: 8 is in the table - return the current index [2] and the value of 8 in the map, which is 0.

因此，最终输出为 2,0 - 正如预期的那样。

---

(1) 复杂性通知:
在这里，O(n) 假定O(1) 哈希函数。这并非总是如此。如果我们确实假设 O(1) 哈希函数，我们也可以假设使用基数排序的排序是 O(n)，并使用 的后处理O(n) [类似于@SteveJessop 在他的回答中建议的]，我们也可以使用基于排序的算法实现 O(n)。