如何在递归分而治之的解决方案中自下而上传递原始数组的索引？

Question

我正在为硬件问题创建一个分而治之的算法。给定一个数组，我需要找到最高值的索引（如果有多个，则为任何索引）。如果我想 return 最高值，我的解决方案有效，但我发现在尝试将索引从堆栈的按钮向上传递时遇到困难。每个级别的数组大小不同。

    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

您必须创建一个 class 对象来存储它们并返回，因此创建一个 class 来存储 1 个数组和 1 个整数 - 例如：

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

Answer 2

您可以将一个偏移量变量传递给您的

方法，而不是创建一个 class 来存储索引，该方法告诉您传递给该方法的数组的第一个元素有多远从第一个函数调用传入的原始数组的第一个元素的右侧。

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

但是，要从原始数组中获取索引，我们还必须更改基本条件。目前，当数组中只剩下一个或更少的元素时，你总是 return 0 。相反，您应该传递偏移量变量，因为这应该表示原始数组中值的索引。

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

现在解决大家最关心的问题，如何准确比较左右数组中出现最大值的索引处的值。事情是这样的：从对 findLargestPos 的函数调用中得到的索引 return 表示原始数组中最大值的索引。但是要访问子数组中的这些值，您必须使用偏移量变量。例如，假设原始数组被分成两个大小为 3 的数组。如果右子数组中的最大值对应于原始数组中的索引 4，则它对应于右子数组中的索引 1。由于本例中的 mid 为 3，因此我们将从索引中减去 offset 以获得用于访问右子数组中的值的适当索引。相同的逻辑适用于左子数组。所以这就是最终方法实现的样子，

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.

的调用

如何在递归分而治之的解决方案中自下而上传递原始数组的索引？

How to pass a index of the original array from buttom up in a recursive divide-and-conquer solution?

java

algorithm

divide-and-conquer