假设我们有两个数组A[n]和b[n],目标是将A中的每个元素与B中的元素进行比较。然后返回一个列表result[n],记录A中每个元素的数量大于 B 中的元素。
例如,
A = [38, 24, 43, 3], B = [9, 82, 10, 11]
由于38大于9、10、11,所以result[0]为3。 则结果为 [3, 3, 3, 0]。
如果能提供一些伪代码最好。
谢谢。
最佳答案
您可以在 O(nlogn) 复杂度中执行上述算法,其中 n 是问题中给出的数组 A 和数组 B 的长度。
算法
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
数组。
总体时间复杂度 - O(nlogn)
。
希望这对您有所帮助!
关于algorithm - 如何比较时间复杂度小于 O(n^2) 的两个数组中的每个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53135373/