Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.3k views
in Technique[技术] by (71.8m points)

algorithm - How to compare each element in two arrays with time complexity less than O(n^2)

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.

For example,

A = [38, 24, 43, 3], B = [9, 82, 10, 11]

Since 38 is larger than 9, 10 and 11, so result[0] is 3. Then result is [3, 3, 3, 0].

It will be the best if you can provide some pseudocode.

Thank you.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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.

Algorithm

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.

At the end you will have res array ready with the answer.

Overall time complexity - O(nlogn).

Hope this helps!


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...