如何以小于 O(n^2) 的时间复杂度比较两个数组中的每个元素

Question

假设我们有两个数组 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。则 result 为 [3, 3, 3, 0]。

如果能提供一些伪代码那就最好了。

谢谢。

Answer 1

您可以以 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).

希望这可以帮助！