检查未排序数组a中是否存在a [i] = 2 * a [j]? [英] check if there exists a[i] = 2*a[j] in an unsorted array a?

问题描述

给定整数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.

Given a unsorted sequence of a[1,...,n] of integers, give an O(nlogn) runtime algorithm to check there are two indices i and j such that a[i] =2*a[j]. The algorithm should return i=0 and j=2 on input 4,12,8,10 and false on input 4,3,1,11.

我认为我们仍然必须对数组进行排序，即O(nlogn).我不确定之后该怎么办.

I think we have to sort the array anyways which is O(nlogn). I'm not sure what to do after that.

推荐答案

您是对的，第一步是对数组进行排序.

You're right that the first step is sorting the array.

对数组进行排序后，您可以在O(log n)时间内找出给定元素是否在数组内.因此，如果对于每个n元素，您在O(log n)时间内检查是否包含另一个元素，则最终运行时为O(n log n).

Once the array is sorted, you can find out whether a given element is inside the array in O(log n) time. So if for every of the n elements, you check for the inclusion of another element in O(log n) time, you end up with a runtime of O(n log n).

这对您有帮助吗?

这篇关于检查未排序数组a中是否存在a [i] = 2 * a [j]?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！