如何比较时间复杂度小于O(n ^ 2)的两个数组中的每个元素 [英] How to compare each element in two arrays with time complexity less than O(n^2)
问题描述
假设我们有两个数组A [n]和b [n],目标是将A中的每个元素与B中的元素进行比较。然后返回一个列表结果[n],该结果记录A中每个元素的数量,
Suppose we have two arrays A[n] and b[n], the goal is to compare every element in A to elements in B. Then return a list result[n] that records the number of each element in A that is larger than the elements in B.
例如,
A = [38,24,43,3],B = [9,82,10,11]
A = [38, 24, 43, 3], B = [9, 82, 10, 11]
因为38大于9 ,10和11,所以result [0]为3。
然后结果为[3、3、3、0]。
Since 38 is larger than 9, 10 and 11, so result[0] is 3. Then result is [3, 3, 3, 0].
这将是最好的
谢谢。
推荐答案
您可以以O(nlogn)复杂度执行上述算法,其中n是问题中给出的数组A和数组B的长度。
You can perform the above algorithm in O(nlogn) complexity where n is the length of array A and array B as given in the question.
1. Sort both the arrays A and B, this will take O(nlogn) time complexity.
2. Take two pointers i and j, initialize both of them to 0. we will use i for array A and j for B.
3. Create a result array res of size n.
4. Start a while loop
while(i<n && j<n) {
if(A[i] > B[j]) {
j++;
} else {
res[i] = j+1;
i++;
}
}
5. while(i<n) {
res[i] = n;
}
This step is for the case where all elements in A are bigger than all elements in B.
最后,您将准备好 res
个带有答案的数组。
At the end you will have res
array ready with the answer.
总时间复杂性- O(nlogn)
。
希望这会有所帮助!
这篇关于如何比较时间复杂度小于O(n ^ 2)的两个数组中的每个元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!