How to replace all elements of an ArrayList with another ArrayList which is of different size?

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note: You have to modify the array A to contain the merge of A and B. Do not output anything in your code. TIP: C users, please malloc the result into a new array and return the result.

If the number of elements initialized in A and B are m and n respectively, the resulting size of array A after your code is executed should be m + n

Example :

Input : 
         A : [1 5 8]
         B : [6 9]

Modified A : [1 5 6 8 9]

My Solution:

public class Solution {
    public void merge(ArrayList<Integer> a, ArrayList<Integer> b) {

        int i=0,j=0;
        ArrayList<Integer> al= new ArrayList<Integer>();

        while(i<a.size() && j<b.size()){
            if(a.get(i)<b.get(j)){
            al.add(a.get(i));
            i++;
        }

        else{
            al.add(b.get(j));
            j++;
        }
    }

    while(i<a.size()){
        al.add(a.get(i));
        i++;
    }

    while(j<b.size()){
        al.add(b.get(j));
        j++;
    }
}

I created a 3rd ArrayList where I merged all elements of both 1st and 2nd ArrayLists. Now I have to copy all the elements of 3rd ArrayList into 1st one. I’m stuck now. Because, when I resized it by using

public static void ensureSize(ArrayList<Integer> list, int size){
    list.ensureCapacity(size);
    while(list.size()<size){
        list.add(null);
    }
}

ensureSize(a,al.size());
for(int k=0;k<al.size();k++){
     a.set(k,al.get(k));
}

It’s giving me ArrayIndexOutOfBound error. I tried Collections.copy(a,al), it too didn’t work.

Answer

As the two given arrays are already sorted

Input : A : [1 5 8] B : [6 9]

Modified A : [1 5 6 8 9]

you could do something like this: Option: 1

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++];

        else        
            answer[k++] = b[j++];               
    }

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


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

    return answer;
}

Note: I have used arrays rather than ArrayList as I think that is what the question is asking for. Also it is really helpful to understand the concept of merging sorted arrays, this link will help.

Another option, if you want to be really snazzy: Option: 2

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

    int[] answer = new int[a.length + b.length]
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] = 
            (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
}

But if you really wanted to use Lists then I would do something like this: Option: 3

public static <T> ArrayList<T> merge(List<T> a, List<T> b) {
    ArrayList<T> result = new ArrayList<T>();
    int size = Math.max(a.size(), b.size());

    for (int i = 0; i < size; i++) {
        if (i < a.size()) result.add(a.get(i));
        if (i < b.size()) result.add(b.get(i));
    }
    return result;
}

If lists really are the only option I probably wouldn’t even use my own algorithm, you could quite simply use built in functions such: Option: 4

List<Integer> all = new ArrayList<Integer>();
all.addAll(list1);
all.addAll(list2);

Collections.sort(all);

This last algorithm works for arrays which aren’t initially in sorted order, which I don’t think you’re looking for but it is an option.

How to execute Option: 3:

public static void main(String[] args){
    List<Integer> l1 = Arrays.asList(1,5,7,9);
    List<Integer> l2 = Arrays.asList(4,3,11);
    System.out.println(merge(l1,l2));
}

From what I gather you also want to merge the new ArrayList with the first ArrayList and remove any duplicates, I would do something like this:

for (Object x : two){
   if (!one.contains(x))
      one.add(x);
}

This has already been answered on this post, check it out

Leave a Reply

Your email address will not be published. Required fields are marked *