merge 2 sorted list with all elements Homework

Question

I have a homework ,and which I have tried to solve for serveral hours.

Description:we have 2 sorted array list ,the length of list a is n, the length of list b is m;we assume a and b are already sorted, and that the lists a and b do not contain duplicates.And I thought as following ,but I always get a error:index out of bound .

public static List<Integer> union(List<Integer> list1, List<Integer> list2 ) {
    List<Integer> union = new ArrayList<>();
    int n1 = 0;
    int n2 = 0;
   

    for (int i = 0; i < list1+list2; i++) {
       ....
}

Your issue lies in when you get to the end of one array and are still trying to grab a value after you increment your index for the compare. You will overshoot your array bounds at that point. You'll need to ensure you don't overshoot and keep pulling from an exhausted array. — Tim Hunter, Oct 23 '20 at 15:02

p_flame · Answer 1 · 2020-10-23T16:00:53.240

If you loop till m + n one of the array which might have a lesser size than the other will get exhausted and hence the array index out of bound. Instead you can use a while loop which will loop only till the minimum size of the two lists and later, since the list is sorted you can add all the remaining elements from the bigger of the two lists into the union

// iterate till the minimum of two lists

while(index1 < a.size() && index2 < b.size()) {
  if (a.get( index1 ) > b.get( index2 )) {
    union.add(i++, b.get( index2++ ));
  }
  else {
    union.add(i++, a.get( index1++ ));
  }
}

//add the elements of the bigger list to the union

while(index1 < a.size()) {
  union.add(i++ ,a.get( index1++ ));
}

while(index2 < b.size()){
  union.add(i++, b.get( index2++ ));
}

score 0 · Answer 2 · answered Oct 23 '20 at 16:27

public static List<Integer> union(List<Integer> one, List<Integer> two) {
    List<Integer> res = new ArrayList<>(one.size() + two.size());

    for (int i = 0, a1 = 0, a2 = 0; i < one.size() + two.size(); i++) {
        if (a1 == one.size())
            res.add(two.get(a2++));
        else if (a2 == two.size())
            res.add(one.get(a1++));
        else
            res.add(one.get(a1) <= two.get(a2) ? one.get(a1++) : two.get(a2++));
    }

    return res;
}

merge 2 sorted list with all elements Homework

2 Answers2