CODEWITHSUNDEEP
javaarraysalgorithmbig-o
sag_dc
sag_dc

Reputation: 99

Merging a collection of unsorted arrays to find common elements

How different would it be to merge a collection of unsorted arrays type Comparable versus the code below?

Comparable [][] collections {colA, colB, colC};

After searching I found a way of merging two sorted array of primitive data.

public static int[] merge(int[] a, int[] b) {

int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
    if (a[i] < b[j])
    {
        answer[k] = a[i];
        i++;
    }
    else
    {
        answer[k] = b[j];
        j++;
    }
    k++;
}

while (i < a.length)
{
    answer[k] = a[i];
    i++;
    k++;
}

while (j < b.length)
{
    answer[k] = b[j];
    j++;
    k++;
}

return answer;

}

Here, How to merge two sorted arrays into a sorted array?

Assuming that I have K arrays (e.g. A & B...), and I want to obtain list C (allowing duplicate items). I want to only compare each element one time. For faster performance even if I compromise on memory.

Thank you!

Upvotes: 0

Views: 375

Answers (2)

Orch
Orch

Reputation: 885

You can use essentially the exact same algorithm you listed. The efficiency is O(nk^2), so it's not optimal but it'll be easy to implement since you already know how to do it for k=2.

Upvotes: 0

amit
amit

Reputation: 178481

If you have k sorted arrays, and you are looking to merge them, you can build a heap (PriorityQueue), that at the beginning is populated by the first element from each list.

Then, until the queue is empty:

  1. Pop the lowest element from the queue
  2. Append the element to the sorted merged list
  3. Add to the queue the next element in the list where the popped element belonged to (if such exists).

This is done in O(nlogk) time, where n is the total number of elements and k is the number of lists. It is easy to show this solution is optimal, because otherwise you could sort an unsorted list better than Omega(nlogn)

Upvotes: 1

Related Questions