由外向内呈螺旋状循环

Question

我正在寻找类似于 Looping in a spiral 的矩阵循环，但循环是从外到内，而不是从内到外。任何人都可以帮助我为任何大小的矩阵执行此操作，最好是 Ruby?

示例：在 3x4 矩阵中，我想从 [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]

Answer 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]

Answer 2

这里 working C code 从外到内顺时针打印二维矩阵。

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' 变量会跟踪我们正在打印的值是否是该 row/col 的第一个值。第一个值不会被打印出来，因为它已经被之前的循环打印出来了。

时间复杂度：O(n)
Space 复杂度：O(1)

其中 n 是数组中元素的数量。

Answer 3

这个方法做你需要的，它循环外层螺旋然后递归调用自己循环内层螺旋

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)

你也可以填充一个矩阵来绘制螺旋线，如果你在每一步都填充它的方向你会得到这样的东西：

→  →  →  →  ↴ 
↱  →  →  ↴  ↓ 
↑  ↱  ↴  ↓  ↓ 
↑  ↑  ↓  ↓  ↓ 
↑  ↑  ↓  ↓  ↓ 
↑  ↑  ↓  ↓  ↓ 
↑  ↑  ↓  ↓  ↓ 
↑  ↑  ✓  ↓  ↓ 
↑  ↑  ←  ⤶  ↓ 
↑  ←  ←  ←  ⤶

Answer 4

这是一个一直让我着迷的问题。 @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]]

这个 gist 中有几个答案也值得一看。

由外向内呈螺旋状循环

Looping in a spiral outside-in

ruby

algorithm

spiral