在外向内螺旋循环

Question

我希望能遍历类似于螺旋式遍历的矩阵，但是我需要从外向内而不是从内向外遍历。有没有人能帮我找到一个好方法来实现这一点，最好是用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]

- ant

---

我使用Ruby编写了一个方法来解决这个问题，它有点冗长，但应该很容易理解它的工作原理： https://gist.github.com/hbejgel/c18b2d54888305dc768d - hbejgel

如果仍然关心重复的话，这里有两个链接：http://stackoverflow.com/questions/28726345/possible-algorithms-for-printing-spiral-matrix/28726589#28726589 和 http://stackoverflow.com/questions/23799776/how-to-build-spiral-square-matrix-using-recursion - 除了它们没有提供Ruby代码，我认为这两个链接中大多数答案都很满意。 - IVlad

欢迎来到 Stack Overflow。在尝试解决问题时向我们展示你所做的努力非常重要。这样可以让我们纠正你自己代码中的错误，而不是将陌生/外来的代码硬塞到你现有的代码中。这是在假设你已经尝试过一些东西，并且不仅仅是希望有人为你编写代码。 - the Tin Man

@theTinMan 说得好。我正在使用这里概述的基本算法 http://stackoverflow.com/questions/28726345/possible-algorithms-for-printing-spiral-matrix/28726589#28726589，但我知道Ruby一定有更优雅的解决方法。我会在未来的问题中发布我的代码！ - ant

可能是螺旋循环的重复问题。 - dgilperez

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] 

- Cary Swoveland

---

谢谢大家，看到你们不同的解决方案真是非常有趣。最终我选择了这个解决方案，因为我喜欢它使用转置来解决问题的方式。 - ant

有趣...就像切掉顶层然后旋转矩阵？所以就像一个块状奶酪，你总是切掉顶部然后旋转奶酪块...现在它不是O(n*m*k)，其中k是min(n,m)，最好的方法应该是O(n*m)了吗？...顺便问一下，如果问题现在是“以螺旋方式填充n * m空矩阵”，就像这个答案中的矩阵一样，会怎么样？ - nonopolarity

@太极者无极而生，我喜欢你的奶酪块。让我想一想你说的话。我会尽量明天回复。 - Cary Swoveland

Answer 2

这是一个一直吸引我的问题。@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里有几个答案也值得一看。

- O-I

---

太好了，看到一行短代码！ - ant

不错，O-I。我喜欢你消除了我的 reverse 映射（matrix.reverse.transpose 也可以工作），以及你使用递归的方式。如果原始矩阵不需要被改变，只需添加 def spiral_starter(matrix); spiral(matrix.map(&:dup)); end。你应该将你的答案框起来。 - Cary Swoveland

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)

如果在每个步骤中都填充一个矩阵以绘制螺旋线，可以填充出您将要执行的方向，如下所示：

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

- hbejgel

---

好漂亮的图形。你是在寻找这个吗：↵？看起来没有左上方向的字符，这很奇怪。 - Cary Swoveland

Answer 4

这里有一份可运行的C代码，可以将一个二维矩阵以从外到内的顺序打印出来。

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”变量跟踪我们正在打印的值是否是该行/列的第一个值。第一个值不会被打印，因为它已经被前面的循环打印过了。

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

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

- Nikunj Banka