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

Question

给定整数[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)使用哈希表在平均¹上完成.

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],然后迭代第一次时,我们插入2*a[j]到所述一组当我们阅读a[j].在第二次迭代中,我们发现它a[i] == 2* a[j]在set中,并返回true.

<=
如果算法返回true,那么它发现a[i]使得a[i]已经在第二次迭代中的集.所以,在第一次itetation期间 - 我们插入a[i].这只是可以做,如果有第二元件a[j],从而a[i] == 2 * a[j],我们插入a[i]阅读时a[j].

注意:
为了返回元素的索引,可以简单地使用散列映射而不是集合,并将每个i存储2*a[i]作为键和i值.

例:
Input = [4,12,8,10]

首先为每个x - 2x插入哈希表和索引.你会得到:

hashTable = {(8,0),(24,1),(16,2),(20,3)}

现在,在secod迭代中,检查每个元素是否在表中:

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)散列函数,我们也可以假设使用radix-sort进行排序O(n),并使用O(n)[类似于@SteveJessop在他的答案中建议的那样]的后处理,我们也可以O(n)使用基于排序的算法来实现.

Answer 2

1. 对数组进行排序(O(n log n)或者,O(n)如果您愿意扩展有关固定大小整数数组的观点)
2. 在数组的开头初始化两个指针("fast"和"slow")(O(1))
3. 反复:
   1. 增加"快速"直到找到偶数值> ="慢"值的两倍
   2. 如果"fast"的值恰好是"slow"值的两倍,则返回true
   3. 增加"慢",直到找到值> =值的一半 fast
   4. 如果"slow"的值恰好是"fast"值的一半,则返回true
4. 如果其中一个增量尝试超过了结束,则返回false

由于每个fast并且在到达阵列末尾之前总共slow可以增加n总数,所以"重复"部分是O(n).

Answer 3

你是对的,第一步是对数组进行排序.

对数组进行排序后,您可以及时了解给定元素是否在数组中O(log n).因此,如果对于每个n元素,检查是否包含其他元素 O(log n),最终会得到运行时的O(n log n).

这对你有帮助吗？