Объединение 2-х отсортированных массивов в 1 в Java

Question

Всем привет! Ребята, помогите, пожалуйста, разобраться в задаче: Реализуйте метод, сливающий два отсортированных по неубыванию массива чисел в один отсортированный в том же порядке массив. Массивы могут быть любой длины, в том числе нулевой.

Предполагается, что вы реализуете алгоритм слияния, имеющий линейную сложность: он будет идти по двум исходным массивам и сразу формировать отсортированный результирующий массив. Так, чтобы сортировка полученного массива при помощи Arrays.sort() уже не требовалась.

Пример ввода: {0, 2, 2} и {1, 3} Пример вывода: {0, 1, 2, 2, 3}. Написала код, но у меня он не работает в случае если в обоих массивах числа отрицательные. Что я делаю не так? Наведите, пожалуйста, на мысль. Заранее спасибо.

public static void main(String[] args) {
 // System.out.println(Arrays.toString(mergeArrays(new int[]{0, 2, 2}, new int[]{1, 3})));
 // System.out.println(Arrays.toString(mergeArrays(new int[]{}, new int[]{})));
 System.out.println(Arrays.toString(mergeArrays(new int[]{-4, -3, -1}, new int[]{-10, -5, -2})));
 //System.out.println(Arrays.toString(mergeArrays(new int[]{}, new int[]{1, 3})));
 }

 public static int[] mergeArrays(int[] a1, int[] a2) {
 int[] a3 = new int[a1.length + a2.length];

 int i = 0, j = 0;
 for (int k = 0; k < a3.length; k++) {
 if ((i > a1.length - 1) || (a1[i] > a2[j])) {
 a3[k] = a2[j];
 j++;
 } else if ((j > a2.length - 1) || (a1[i] < a2[j])) {
 a3[k] = a1[i];
 i++;
 } else {
 a3[k] = a2[j];
 j++;
 }
 }
 return a3;
 }
}

Answer 1

Оператор

if ((i > a1.length - 1) || (a1[i] > a2[j]))

будет обращаться ко второму массиву, даже если он кончился.

Отделите проверки индексов от сравнения значений.

Проще всего сделать три цикла. В первом основное слияние, еще в двух дописка неиспользованных остатков, если они есть.

while ((i < a1.length) && (j < a2.length)) {
  if (a1[i] <= a2[j]) 
    ...
}
while (i < a1.length) {
} 
while (j < a2.length) {
}

Answer 2

Давно пользуюсь такой функцией, попробуйте:

public static int[] merge(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int i = 0, j = 0, r = 0;
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result[r] = arr1[i];
            i++;
        } else {
            result[r] = arr2[j];
            j++;
        }
        r++;
    }
    if (i < arr1.length) {
        System.arraycopy(arr1, i, result, r, (arr1.length - i));
    }
    if (j < arr2.length) {
        System.arraycopy(arr2, j, result, r, (arr2.length - j));
    }
    return result;
}

БЛОГ НА HUSL

Объединение 2-х отсортированных массивов в 1 в Java

Ответы (2 шт):