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

Question

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.

Did you notice that the assignment is talking about arrays, but your code is using ArrayList? — Kayaman
– Kayaman, Commented Jun 15, 2016 at 11:57
The exception is telling you exactly what's wrong, and exactly where in the code the problem is. Read the exception's description in the JavaDoc, and step through the code with a debugger. — T.J. Crowder
– T.J. Crowder, Commented Jun 15, 2016 at 11:57
@Kayamanpublic ** class Solution { public void merge(ArrayList<Integer> a, ArrayList<Integer> b) { } } ** This will be provided in the editor. — tourist
– tourist, Commented Jun 15, 2016 at 11:58
Since this question looks a lot like homework, I will not give the answer, just a pointer to try to help out. In Java, a Collection has no "fixed size", but rather will check its limit on operations, and adjust. If you create an response ArrayList, you can just cicle trough each array, check if the List already contains the watched Object, and insert if needed. — Bonatti
– Bonatti, Commented Jun 15, 2016 at 11:59

Community · Accepted Answer · 2017-05-23 11:52:50Z

5

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

edited May 23, 2017 at 11:52

CommunityBot

11 silver badge

answered Jun 15, 2016 at 12:08

Luke Garrigan

5,0811 gold badge26 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

tourist Over a year ago

Thanks for the detailed explanation. Option 1 is completely a simplest approach however, I'm allowed to use only List. Option 3 is helpful. And I'd be glad if you could tell me what I have to do after my code snippet 1.

Luke Garrigan Over a year ago

I have changed Option 3 a little, maybe this helps @BhaskarSantoshK and I have added how you would execute it

tourist Over a year ago

Thanks a lot for your help. I'd like to mention something which needs attention is that, here in the question, you're allowed to use an extra memory however at the end, the result will be compared only with the first list given as argument. So, could you please tell me how can I copy my list al into a ? (a and al are different in size)

tourist Over a year ago

A comment made above was like this: Since this question looks a lot like homework, I will not give the answer, just a pointer to try to help out. In Java, a Collection has no "fixed size", but rather will check its limit on operations, and adjust. If you create an response ArrayList, you can just cicle trough each array, check if the List already contains the watched Object, and insert if needed This.. I would like to understand

tourist Over a year ago

for (Object x : two){ if (!one.contains(x)) one.add(x); } This will merge the arrays, but the resulting array might not be in a sorted order..

|

AGBajwa · Accepted Answer · 2016-06-15 12:24:10Z

0

To complete the answer please add following code to the above solution before return answer;

a = new int[answer.length];
a = Arrays.copyOf(answer, answer.length);

and change

return answer;

to

return a;

answered Jun 15, 2016 at 12:24

AGBajwa

1

1 Comment

tourist Over a year ago

Thanks.. It can easily be done if I am allowed to use arrays. My question is something different.

Adam · Accepted Answer · 2016-06-15 12:31:42Z

I believe this can be solved more simply using the following.

Maintain indexes to both arrays, and read from the smaller element.
I'd recommend always using for loops rather than while() loops, they're easier to reason with.
Avoid using variables like i and j, a recipe for typos...

Example

int[] a = { 1, 5, 8 };
int[] b = { 6, 9 };

int aPos = 0;
int bPos = 0;
int n = a.length + b.length;

int[] result = new int[n];
for (int i = 0; i < n; i++) {
    if (aPos == a.length) {
        // at end of A, must use B
        result[i] = b[bPos++];
    } else if (bPos == b.length) {
        // at end of B, must use A
        result[i] = a[aPos++];
    } else if (a[aPos] < b[bPos]) {
        result[i] = a[aPos++];
    } else {
        result[i] = b[bPos++];
    }
}
System.out.println(Arrays.toString(result));

Collectives™ on Stack Overflow

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

3 Answers 3

9 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related