从外面盘旋
我希望循环一个类似于循环的矩阵，但是从外向内循环，而不是从里到外循环。 任何人都可以帮助我为任何大小的矩阵做一个好的方法，理想情况下在Ruby中吗？
示例：在3×4矩阵中，我想从右边的[0,0]开始，然后在到达[3,0]时向下移动，在[3,2]等处向左移动。
[0,0] [1,0] [2,0] [3,0] [0,1] [1,1] [2,1] [3,1] [0,2] [1,2] [2,2] [3,2] 移动顺序如下所示：
0 1 2 3 9 10 11 4 8 7 6 5
输出将是：
[0,0], [1,0], [2,0], [3,0], [3,1], [3,2], [2,2], [1,2], [0,2], [0,1], [1,1], [2,1]
不失一般性，让我们把数组写成：
arr = [ [ 1, 2, 3, 4,], [12, 13, 14, 5,], [11, 16, 15, 6,], [10, 9, 8, 7,] ]
期望的结果是：
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
我会用一个帮手：
def rotate_anticlockwise(arr) arr.map(&:reverse).transpose end
例如：
rotate_anticlockwise(arr) #=> [[4, 5, 6, 7], # [3, 14, 15, 8], # [2, 13, 16, 9], # [1, 12, 11, 10]]
我们现在可以如下计算所需的结果：
out = [] a = arr.map(&:dup) while a.any? out.concat(a.shift) a = rotate_anticlockwise(a) end out # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
这个问题一直令我着迷。 @CarySwoveland的诀窍让它在Ruby中非常优雅。 这是一个单行方法：
def spiral(matrix) matrix.empty? ? [] : matrix.shift + spiral(matrix.transpose.reverse) end arr = [[ 1, 2, 3, 4,], [12, 13, 14, 5,], [11, 16, 15, 6,], [10, 9, 8, 7,]] spiral(arr) # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
然而，这种方法的一个缺陷是它改变了原始矩阵arr ：
arr # => [[12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]
这个要点有几个答案值得一看。
这是工作C代码 ，从外到内以顺时针方式打印2D矩阵。
int n = 2, m = 5; int arr[2][5] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int top = 0, bottom = n-1, right = m-1, left = 0, i=0, j=0; printf("%d ", arr[i][j]); while(1){ if(top>bottom || left>right) break; if(bottom==top){ for(j=left; j<=right; j++) printf("%d ", arr[top][j]); break; } if(right==left){ for(i=top; i<=bottom; i++) printf("%d ", arr[left][i]); break; } int first = 1; while(j<=right){ if(first){ j++; first = 0; continue; } printf("%d ", arr[i][j]); j++; } j--; right--; first = 1; while(i<=bottom){ if(first){ i++; first = 0; continue; } printf("%d ", arr[i][j]); i++; } i--; bottom--; first = 1; while(j>=left){ if(first){ j--; first = 0; continue; } printf("%d ", arr[i][j]); j--; } j++; left++; first = 1; while(i>=top+1){ if(first){ i--; first = 0; continue; } printf("%d ", arr[i][j]); i--; } i++; top++; }
代码背后的逻辑和推理是你保持到目前为止尚未打印的矩阵的边界。 所以在程序开始时，顶部边界= 0，底部= n-1，左边= 0，右边= n-1。
在外部while循环中的每次迭代中，检查由边界定义的剩余矩阵是否退化为行或列矩阵。 或者，如果已经打印了矩阵的所有元素，之后它就会突然出现循环。
此外，每个内部while循环中的“first”变量会跟踪我们正在打印的值是否是该行/ col的第一个值。 第一个值将不会被打印，因为它已经在它之前的循环中打印出来。
时间复杂度： O(n)
空间复杂度： O(1)
其中n是数组中元素的数量。
这个方法可以满足你的需要，它循环通过外部螺旋，然后递归地调用自身来循环内部螺旋
def inward_spiral(height, width, current_height, current_width) if height <= 0 || width <= 0 return end # Right (width-1).times do puts "[#{current_width}, #{current_height}]" current_width += 1 end # Down (height-1).times do puts "[#{current_width}, #{current_height}]" current_height += 1 end # Left if height > 1 (width-1).times do puts "[#{current_width}, #{current_height}]" current_width -= 1 end end # Up if width > 1 (height-2).times do puts "[#{current_width}, #{current_height}]" current_height -= 1 end end puts "[#{current_width}, #{current_height}]" inward_spiral(height-2, width-2, current_width + 1, current_height) end
然后称之为inward_spiral(3,4,0,0)
您还可以填充一个矩阵来绘制螺旋线，如果在每个步骤中填充它，您将获得如下所示的方向：
→ → → → ↴ ↱ → → ↴ ↓ ↑ ↱ ↴ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ✓ ↓ ↓ ↑ ↑ ← ⤶ ↓ ↑ ← ← ← ⤶