Слияние двух отсортированных массивов в Java рекурсивно

Question

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

public static char[] mergeArrays( char[] A, char[] B) {

    char[] answer = new char[ 0];  // an empty array to have something to return

        return mergeArraysHelper(A, B, 0);

    }

public static char[] mergeArraysHelper(char[] a, char[] b, int index) {
    char[] newArr = new char[a.length+b.length];
    if(index > newArr.length) {
        return newArr;
    } 

    //check to see if both arrays are still populated
    if(index < a.length && index < b.length) {
        newArr[index] = a[index];
        newArr[index+1] = b[index];
    } else {
        //check to see if array a is empty
        if(index > a.length && index < b.length) {
            newArr[index] = b[index];
        } else {
            //check to see if array b is empty
            if(index < a.length && index > b.length) {
                newArr[index] = a[index];
            } else {
                return newArr;
            }
        }
    }
    mergeArraysHelper(a, b, ++index);
    return newArr;
}

Answer 1

Мне нравится это решение:

public static char[] mergeArrays(char[] a, char[] b) {
    if(a.length == 0)
        return b;

    if(b.length == 0)
        return a;

    char[] newArr = new char[a.length + b.length];
    if(a[0] <= b[0]) {
        newArr[0] = a[0];
        char[] merged = mergeArrays(Arrays.copyOfRange(a, 1, a.length), b);
        System.arraycopy(merged, 0, newArr, 1, merged.length);
    } else {
        newArr[0] = b[0];
        char[] merged = mergeArrays(a, Arrays.copyOfRange(b, 1, b.length));
        System.arraycopy(merged, 0, newArr, 1, merged.length);
    }

    return newArr;
}

Но если вы не хотите каждый раз создавать новый массив, вы можете предпочесть сделать что-то вроде этого:

public static char[] mergeArrays( char[] A, char[] B) {
    char[] sorted = new char[A.length + B.length];
    mergeArraysHelper(A, B, sorted, 0);
    return sorted;
}

public static void mergeArraysHelper(char[] a, char[] b, char[] sorted, int index) {
    if(a.length == 0) {
        System.arraycopy(b, 0, sorted, index, b.length);
        return;
    }

    if(b.length == 0) {
        System.arraycopy(a, 0, sorted, index, a.length);
        return;
    }

    if(a[0] <= b[0]) {
        sorted[index] = a[0];
        mergeArraysHelper(Arrays.copyOfRange(a, 1, a.length), b, sorted, index + 1);
    } else {
        sorted[index] = b[0];
        mergeArraysHelper(a, Arrays.copyOfRange(b, 1, b.length), sorted, index + 1);
    }
}

Answer 2

Вы должны передавать newArr в каждый рекурсивный вызов, не создавайте новый экземпляр каждый раз. В этом случае вам вообще не нужно ничего возвращать из рекурсивного вызова. Ваш метод обертки будет выглядеть так:

public static char[] mergeArrays( char[] A, char[] B) {
    char[] answer = new char[ 0];  // an empty array to have something to return
    char[] newArr = new char[ A.length + B.length];
    mergeArraysHelper(newArr, A, B, 0);
    return newArr;
}