Как передать индекс исходного массива снизу вверх в рекурсивном решении «разделяй и властвуй»?

Question

Я создаю алгоритм «разделяй и властвуй» для задачи HW. Учитывая массив, мне нужно найти индекс наибольшего значения (любой индекс, если есть несколько). Мое решение работает, если я хочу вернуть самое высокое значение, но я испытываю трудности при попытке передать индекс из нижней части стека обратно. Размер массива различен для каждого уровня.

    int findLargestPos(int[] arr) {
        int n = arr.length;
        int mid = (int)Math.floor(arr.length / 2);

        if (arr.length <= 1) {
            return 0;
        }

        int[] arr2 = new int[mid];
        int[] arr3 = new int[arr.length - mid];

        copyArr(arr, arr2, 0, 0);
        copyArr(arr, arr3, mid, 0);

        int index1 = findLargestPos(arr);
        int index2 = findLargestPos(arr);

        // Problem starts
        if (value from arr2 is greater than arr3) {
            return arr2 index
        }

        return arr3 index
    }

Answer 1

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

int findLargestPos(int[] arr, int offset) {
    ...
}

Таким образом, при первом вызове findLargestPos переданное смещение должно быть 0.

findLargestPos(arr, 0)

При дальнейших рекурсивных вызовах findLargestPos смещение передается для левого массива. должно быть смещением, переданным для текущего вызова функции, тогда как смещение, переданное для правого массива, должно быть смещением, переданным для текущего вызова функции, плюс mid.

int index1 = findLargestPos(arr2, offset); // left array
int index2 = findLargestPos(arr3, offset + mid); // right array

Однако, чтобы получить индексиз исходного массива мы также должны изменить базовое условие. В настоящее время вы всегда возвращаете 0, когда в массиве остается только один или менее элементов. Вместо этого вы должны передать переменную смещения, поскольку она должна представлять индекс значения в исходном массиве.

if (arr.length <= 1) {
    return offset;
}

Теперь, чтобы решить вашу главную проблему, как точно сравнить значения в индексахлевый и правый массивы, где встречаются самые большие значения. Вот в чем дело: индексы, возвращаемые при вызовах функций findLargestPos, представляют индексы наибольших значений в исходном массиве. Но для доступа к этим значениям в подмассивах необходимо использовать переменные смещения. Например, предположим, что исходный массив был разделен на два массива размером 3. Если наибольшее значение в правом подмассиве соответствует индексу 4 в исходном массиве, то это соответствует индексу 1 в правом подмассиве. Так как mid в этом случае получается равным 3, мы вычли бы смещение из индекса, чтобы получить соответствующий индекс для доступа к значению в правом подмассиве. Та же логика применяется для левого подмассива. Итак, вот как будет выглядеть окончательная реализация метода:

public static int findLargestPos(int[] arr, int offset) {
    int n = arr.length;
    int mid = (int)Math.floor(arr.length / 2);

    if (arr.length <= 1) {
        return offset;
    }

    int[] arr2 = new int[mid];
    int[] arr3 = new int[arr.length - mid];

    System.arraycopy(arr, 0, arr2, 0, mid);
    System.arraycopy(arr, mid, arr3, 0, arr.length - mid);

    int index1 = findLargestPos(arr2, offset);
    int index2 = findLargestPos(arr3, offset + mid);

    if (arr[index1 - offset] > arr[index2 - offset]) {
        return index1;
    }

    return index2;
}

Обратите внимание, что я заменил ваши звонки на copyArr звонками на System.arraycopy.

Answer 2

Вам нужно будет создать объект класса, который будет хранить их оба для возврата, поэтому создайте класс, который будет хранить 1 массив и 1 целое число - например:

class ArrayDetails {
 int[] array;
 int index;
 ArrayDetaild(array, index) {
  this.array = array;
  this.index = index;
 }
}