java - 递归输出一个新数组？

Question

奇怪的是，我在整个互联网上没有找到任何有关此问题的信息。当然，对于家庭作业......，我必须递归地将一个元素添加到已排序数组中的正确位置。问题是 - 由于 java 中的数组具有固定大小，我无法更改当前的数组，因此我必须创建一个新数组。如果没有递归，这很容易，但由于明显的原因，以下代码不起作用:

static int[] recursivelyInsertElement(int[] array, int index, boolean isAdded, int elem) {

    // Takes a sorted array with index = 0 (because.... recursion), an element
    // we'd like to insert and a boolean (default: false) to prevent us from
    // inserting the element more than once. 

    int[] newArray = new int[array.length + 1];

    if (index >= array.length && isAdded) {
        return newArray;
    }

    if (index >= array.length && !isAdded){
        newArray[index] = elem;
        return newArray;
    }

    if (array[index] > elem && !isAdded) {
        newArray[index] = elem;
        isAdded = true;
    }

    newArray[index] = array[index];
    return recursivelyInsertElement(array, index + 1, isAdded, elem);
}


public static void main(String[] args) {

    int[] array = { 1, 3, 5, 7, 9, 11, 45 };

    int elem = 6;

    int[] newArray = recursivelyInsertElement(array, 0, false, elem);

    for (int index = 0; index < newArray.length; index++) {
        System.out.print(newArray[index] + " ");
    }

}


// Expected output: 1 3 5 6 7 9 11 45 
// Actual output: 0 0 0 0 0 0 0 0 
// The obvious issue here is that a new array is initialized on every step.
// What I'd like to do is avoid this.

所以我想知道 - 我应该如何处理这个问题？创建第二个函数来将新数组中的元素相加？尽管我很确定分配的目标是让我的 recursivelyInsertElement() 返回新数组本身。

附注如果您只给我建议和提示，而不是完整的解决方案，我将不胜感激!

Answer 1

一些提示...

1. 你只需要分配一个新数组一次 - 那就是当你已找到正确的位置并即将插入新的元素。
2. 创建新数组时，必须复制其中的所有值将旧数组放入新数组中，移动元素的索引比新元素大 1，为其留出空间。
3. 插入新元素后，您就完成了，只需将新数组一直返回到堆栈。
4. 1 和 3 组合意味着您永远不会将新数组传递给递归调用:您只需传入原始数组并返回新数组(直接或作为递归结果)。
5. 每次递归调用只会增加索引 - 保证在某个时刻返回。

如果这已经足够了，那么就到这里为止......!

所以，你的 main 函数很好，你的插入函数应该是这样的:

  if index >= array.length
    // run out of array so add to end
    create new array and copy existing data
    add new element at end of array
    return new array

  if array[index] > elem
    // found the first element greater than the candidate so insert before it
    create new array and copy existing data
    add new element at index
    return new array

  // not found so call again with the next index
  return recusrivelyInsertElement(array, index + 1, elem)

请注意，isAdded 标志已消失，如第 3 点所示。

希望这有帮助