arrays - Outside-In二维数组算法

Question

我得到了一系列非负整数。

43 18 5 67 1 72 16 17 15 93 38 6 83 10 49 98 7 47 61 52 71 79 82 52 8

我需要将它存储在 Outside-In 的 m * n 数组中。如下:

m = 5
n = 5

然后，我需要计算二维数组某些部分的总和。 (我已经完成了这部分)。

我理想的存储数字的方法:

 1. Initialize starti,startj = 0.
 2. Initialize endi = m , endj = n.
 3. Store the remaining numbers in array[starti][j], where j starts from startj and ends at endj.
 4. Store the remaining numbers in array[i][endj], where i starts from starti and ends at endi.
 5. Store the remaining numbers in array[endi][j], where j starts from endj and ends at startj.
 6. Store the remaining numbers in array[i][endj], where i starts from endi and ends at starti.
 7. Decrement endi and endj by 1. 
 8. Increment starti and start j by 1.
 9. Repeat the steps 3 - 8 until the last number is stored.

问题:有没有更好的办法解决这个问题？

附加:我一直在尝试(但失败了)使用公式在执行所有这些操作之前找到最后一个元素的存储位置。

Answer 1

这是一种方法。

首先你可以开始递归思考

有一个方法，其签名如`fill(m,n,starting_position, direction)

递归版本看起来像

fill(m,n, starting_position, direction) {

// If m=0 or n=0 you have a base case.
// Start at starting position, and fill in the direction.
// Decrement m or n, depending on the direction
// Compute new starting position and direction
// Recursively call fill with the updated m,n, starting_pos, direction
}

现在请注意，此方法是尾递归的，因此您可以摆脱递归并将其替换为 while 循环，while 循环的条件从基本情况派生。