java merge 2带所有元素的排序列表

Question

我有一个家庭作业，几个小时来我一直在努力解决这个问题

描述：我们有2个排序数组列表，列表a的长度是n，列表b的长度是m；我们假设a和b已经排序，并且列表a和b不包含重复项。我的想法如下，但我总是得到一个错误：索引越界

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++) {
       ....
}

Answer 1

如果循环到m + n其中一个数组的大小可能小于另一个数组，那么该数组将耗尽，因此数组索引将超出范围。相反，您可以使用while循环，该循环将只循环到两个列表的最小大小，然后再循环，因为列表已排序，您可以将两个列表中较大的所有剩余元素添加到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++ ));
}

Answer 2

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;
}