logo标签列表

以螺旋顺序打印二维数组

arraysalgorithmlanguage-agnosticmath
59

我如何以螺旋顺序打印一个5×5的二维数组？

是否有任何公式可以让我按照螺旋顺序打印任何大小的数组？

6
在什么背景下？HTML？WPF？命令行？Matlab？空中写字？ - Tom Ritter
也许他正在解决这个Project Euler问题：http://projecteuler.net/index.php?section=problems&id=28 - Chris Upchurch
38个回答
81

这个想法是将矩阵视为一系列层，即右上角层和左下角层。为了螺旋打印矩阵，我们可以从这些矩阵中剥离层，打印剥离的部分，并对剩余部分进行递归调用打印。当我们没有更多的层要打印时，递归终止。

输入矩阵：

1 2 3 4 
5 6 7 8
9 0 1 2   
3 4 5 6 
7 8 9 1
在剥掉右上角的一层后：
 1 2 3 4 
       8
5 6 7  2
9 0 1  6   
3 4 5  1 
7 8 9

从子矩阵中剥离左下角层后:

   6 7
5  0 1   
9  4 5
3 
7 8 9

从子矩阵中剥离右上方的一层后：

    6 7
      1   
   0  5
   4

从子矩阵中剥离左下角层之后：

  0
  4

递归终止。

C 函数：

// function to print the top-right peel of the matrix and 
// recursively call the print bottom-left on the submatrix.
void printTopRight(int a[][COL], int x1, int y1, int x2, int y2) {
    int i = 0, j = 0;

    // print values in the row.
    for(i = x1; i<=x2; i++) {
        printf("%d ", a[y1][i]);
    }

    // print values in the column.
    for(j = y1 + 1; j <= y2; j++)         {
        printf("%d ", a[j][x2]);
    }

    // see if more layers need to be printed.
    if(x2-x1 > 0) {
        // if yes recursively call the function to 
        // print the bottom left of the sub matrix.
        printBottomLeft(a, x1, y1 + 1, x2-1, y2);
    }
}

// function to print the bottom-left peel of the matrix and 
// recursively call the print top-right on the submatrix.
void printBottomLeft(int a[][COL], int x1, int y1, int x2, int y2) {
    int i = 0, j = 0;

    // print the values in the row in reverse order.
    for(i = x2; i>=x1; i--) {
        printf("%d ", a[y2][i]);
    }

    // print the values in the col in reverse order.
    for(j = y2 - 1; j >= y1; j--) {
        printf("%d ", a[j][x1]);
    }

    // see if more layers need to be printed.
    if(x2-x1 > 0) {
        // if yes recursively call the function to 
        // print the top right of the sub matrix.
        printTopRight(a, x1+1, y1, x2, y2-1);
    }
}

void printSpiral(int arr[][COL]) {
    printTopRight(arr,0,0,COL-1,ROW-1);
    printf("\n");
}
2
请问，x2 - x1的逻辑是什么？ - Sikret Miseon
对于 M * N 矩阵，我们需要检查行和列之间的最大值。然后它将适用于任何矩阵。谢谢。 - Trying
2
@codaddict 在 printBottomLeft 函数中，停止条件不应该是 y2-y1 吗？ - ordinary
2
借助矩阵旋转，问题变得更简单: 先打印顶部行，然后使用其余行向逆时针方向旋转的方式调用该函数。当没有行时，递归完成。 - Wayne Conrad
递归基本情况错误。如果列数大于行数，则此算法将失败，printTopRight中的基本情况应为if (x2- x1> 0 && y1！= y2)。我已经将此代码移植到C＃中，并使用正确的基本情况和文本情况使其适用于任何“n x m”矩阵。 - Abdul Rauf
显示剩余2条评论
34
  1. 弹出顶部行
  2. 转置并翻转（与逆时针旋转90度相同）
  3. 回到1

Python 2 代码:

import itertools

arr = [[1,2,3,4],
       [12,13,14,5],
       [11,16,15,6],
       [10,9,8,7]]

def transpose_and_yield_top(arr):
    while arr:
        yield arr[0]
        arr = list(reversed(zip(*arr[1:])))

print list(itertools.chain(*transpose_and_yield_top(arr)))

对于 Python 3x：

import itertools

arr = [[1,2,3,4],
       [12,13,14,5],
       [11,16,15,6],
       [10,9,8,7]]

def transpose_and_yield_top(arr):
while arr:
    yield arr[0]
    arr = list(reversed(list(zip(*arr[1:]))))


print(list(itertools.chain(*transpose_and_yield_top(arr))))
1
为什么在这里使用yield而不是return？ - Awesome_girl
这个解决方案非常漂亮。谢谢。 我将其用作：rotate = lambda a: list(a[0]) + rotate(zip(*a[1:])[::-1]) if a else [] - tchar
简单而优雅的解决方案！ - Srini
2
优雅简洁（Pythonic）。但请注意，这并不是非常高效的算法，时间复杂度为O(n^3)，因为它在每次迭代中都要遍历整个二维数组（大小递减）。 - justhalf
24
我看到代码中没有人只使用一个for循环且不使用递归，所以我想做出贡献。
思路如下：
设想有一只乌龟站在点(0,0)，即左上角，面向东方（向右）。 它将继续向前走，每次遇到一个符号，乌龟就会向右转。 因此，如果我们把乌龟放在点(0,0)面向右边，如果我们在适当的位置放置符号，乌龟将螺旋式地遍历数组。
现在问题是：“在哪里放符号？”
让我们看看应该放置符号的位置（由#标记，数字由O表示）：
对于像这样的网格： O O O O O O O O O O O O O O O O
我们将符号放在这样的位置： O O O # # O # O O # # O # O O #
对于像这样的网格： O O O O O O O O O O O O
我们将符号放在这样的位置： O O # # # O O # O # O #
对于像这样的网格： O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O
我们将符号放在这样的位置： O O O O O O # # O O O O # O O # O O # O O O # O O O # O # O O O O O #
我们可以看到，除非点位于左上部分，否则符号放置在距离最近的水平边界和垂直边界距离相同的点上，而对于左上部分，则顶部边界的距离比左侧边界的距离多1，如果点处于水平中心，则优先考虑右上角，在点位于垂直中心时优先考虑左上角。
这可以通过一个简单的函数轻松实现，方法是取(curRow和height-1-curRow)的最小值，然后取(curCol和width-1-curCol)的最小值，并比较它们是否相同。 但是，我们需要考虑左上角的情况，即当最小值为curRow和curCol本身时。 在这种情况下，我们相应地减少了垂直距离。
以下是C代码：
#include <stdio.h>

int shouldTurn(int row, int col, int height, int width){
    int same = 1;
    if(row > height-1-row) row = height-1-row, same = 0; // Give precedence to top-left over bottom-left
    if(col >= width-1-col) col = width-1-col, same = 0; // Give precedence to top-right over top-left
    row -= same; // When the row and col doesn't change, this will reduce row by 1
    if(row==col) return 1;
    return 0;
}

int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
void printSpiral(int arr[4][4], int height, int width){
    int directionIdx=0, i=0;
    int curRow=0, curCol=0;
    for(i=0; i<height*width; i++){
        printf("%d ",arr[curRow][curCol]);
        if(shouldTurn(curRow, curCol, height, width)){
            directionIdx = (directionIdx+1)%4;
        }
        curRow += directions[directionIdx][0];
        curCol += directions[directionIdx][1];
    }
    printf("\n");
}

int main(){
    int arr[4][4]= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    printSpiral(arr, 4, 4);
    printSpiral(arr, 3, 4);
}

输出结果为：

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
1 2 3 4 8 12 11 10 9 5 6 7
不错的想法。在这种情况下，该数组从左到右、从上到下排序。如果是这样，这个解决方案能否进一步优化？ - yalkris
为什么我要让一行变长呢？当前的代码是正确的（从输出结果可以看出），因为当 same 不在左上角区域时，它的值已经被更新为 0。 - justhalf
1
将右上角的优先级高于左上角。尝试使用{{1,2,3},{4,5,6},{7,8,9},{10,11,12}}。您应该在5处转向，但是根据您上面的逻辑，shouldTurn返回row = 1和column = 1的0。 - yalkris
1
@ArifNadeem：嗨，Arif，directions数组是一个包含四个元素的数组，每个元素都指定了坐标系中的一个方向：右（0,1），下（1,0），左（0，-1），上（-1,0）。这是因为当你向右移动时，例如，你不会改变行数（一对数字中的第一个数字为0），但你会增加列数（一对数字中的第二个数字为1）。其他三对数字同理。你可以看到这些数字在包含curRow += directions[directionIdx][0]和curCol += directions[directionIdx][1]的行中如何使用。请注意，当你向下移动时，行号会增加。 - justhalf
1
@ArifNadeem：感谢夸奖。然而，这个算法或者任何算法都至少是O(n^2)，因为它需要访问数组中的所有条目。=) - justhalf
显示剩余6条评论
8

以下是三种有趣的方法

  1. Reading in spiral way can be treated like a snake moving towards boundary and turning on hitting the boundary or itself (I find it elegant and most efficient being a single loop of N iterations)

    ar = [
     [ 0,  1,  2,  3, 4],
     [15, 16, 17, 18, 5],
     [14, 23, 24, 19, 6],
     [13, 22, 21, 20, 7],
     [12, 11, 10, 9, 8]]

def print_spiral(ar):
    """
    assuming a rect array
    """
    rows, cols = len(ar), len(ar[0])
    r, c = 0, -1 # start here
    nextturn = stepsx = cols # move so many steps
    stepsy = rows-1
    inc_c, inc_r = 1, 0 # at each step move this much
    turns = 0 # how many times our snake had turned
    for i in range(rows*cols):
        c += inc_c
        r += inc_r 

        print ar[r][c],

        if i == nextturn-1:
            turns += 1
            # at each turn reduce how many steps we go next
            if turns%2==0:
                nextturn += stepsx
                stepsy -= 1
            else:
                nextturn += stepsy
                stepsx -= 1
            # change directions
            inc_c, inc_r = -inc_r, inc_c  

print_spiral(ar)

输出：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  1. A recursive approach would be to print outer layer and call same function for inner rectangle e.g. 

    def print_spiral(ar, sr=0, sc=0, er=None, ec=None):
    er = er or len(ar)-1
    ec = ec or len(ar[0])-1

    if sr > er or sc > ec:
        print
        return

    # print the outer layer
    top, bottom, left, right = [], [], [], []
    for c in range(sc,ec+1):
        top.append(ar[sr][c])
        if sr != er:
            bottom.append(ar[er][ec-(c-sc)])

    for r in range(sr+1,er):
        right.append(ar[r][ec])
        if ec != sc:
            left.append(ar[er-(r-sr)][sc])

    print " ".join([str(a) for a in top + right + bottom + left]),

    # peel next layer of onion
    print_spiral(ar, sr+1, sc+1, er-1, ec-1)

最后，这里有一个小片段可以实现它，虽然不是很高效但很有趣 :)，基本上它会打印顶行，并逆时针旋转整个矩形并重复。

def print_spiral(ar):
    if not ar: return
    print " ".join(str(a) for a in ar[0]),
    ar = zip(*[ reversed(row) for row in ar[1:]])
    print_spiral(ar)
1
我刚刚意识到这与我试图实现的类似，但我使用了不同的方法来找出何时转向。计算步数也是一个好主意！ - justhalf
6
这个程序适用于任何 n*n 矩阵。
public class circ {
    public void get_circ_arr (int n,int [][] a)
    {
        int z=n;
        {
            for (int i=0;i<n;i++)
            {
                for (int l=z-1-i;l>=i;l--)
                {
                    int k=i;
                    System.out.printf("%d",a[k][l]);
                }           

                for (int j=i+1;j<=z-1-i;j++)
                {
                    int k=i;
                    {
                        System.out.printf("%d",a[j][k]);
                    }
                }

                for (int j=i+1;j<=z-i-1;j++)
                {
                    int k=z-1-i;
                    {
                        System.out.printf("%d",a[k][j]);
                    }
                }

                for (int j=z-2-i;j>=i+1;j--)
                {
                    int k=z-i-1;        
                    {
                        System.out.printf("%d",a[j][k]);
                    }
                }
            }
        }
    }
}

希望这能有所帮助。
5

当我学习 Ruby 时，我非常困扰于这个问题。以下是我所能做到的最好的办法：

def spiral(matrix)
  matrix.empty? ? [] : matrix.shift + spiral(matrix.transpose.reverse)
end

您可以通过回溯此“gist”中的修订版本来查看我其他的解决方案。点此访问它。此外，如果您跟随我借鉴这个“gist”的人的链接，您会发现其他一些聪明的解决方案。这是一个非常有趣的问题，可以用多种优雅的方式解决——尤其是在Ruby中。
3

JavaScript解决方案：

var printSpiral = function (matrix) {
  var i;
  var top = 0;
  var left = 0;
  var bottom = matrix.length;
  var right = matrix[0].length;

  while (top < bottom && left < right) {

    //print top 
    for (i = left; i < right; i += 1) {
      console.log(matrix[top][i]);
    }
    top++;

    //print right column
    for (i = top; i < bottom; i += 1) {
      console.log(matrix[i][right - 1]);
    }
    right--;

    if (top < bottom) {
      //print bottom
      for (i = right - 1; i >= left; i -= 1) {
        console.log(matrix[bottom - 1][i]);
      }
      bottom--;
    }

    if (left < right) {
      //print left column
      for (i = bottom - 1; i >= top; i -= 1) {
        console.log(matrix[i][left]);
      }
      left++;
    }
  }
};
2

保持简单 -->

public class spiralMatrix {

public static void printMatrix(int[][] matrix, int rows, int col)
{
    int rowStart=0;
    int rowEnd=rows-1;
    int colStart=0;
    int colEnd=col-1;

    while(colStart<=colEnd && rowStart<=rowEnd)
    {
        for(int i=colStart;i<colEnd;i++)
            System.out.println(matrix[rowStart][i]);

        for(int i=rowStart;i<rowEnd;i++)
            System.out.println(matrix[i][colEnd]);

        for(int i=colEnd;i>colStart;i--)
            System.out.println(matrix[rowEnd][i]);

        for(int i=rowEnd;i>rowStart;i--)
            System.out.println(matrix[i][colStart]);
        rowStart++;
        colEnd--;
        rowEnd--;
        colStart++;

    }

}
public static void main(String[] args){

    int[][] array={{1,2,3,4},{5,6,7,8}};
    printMatrix(array,2,4);
}

}

2
这是我更加清晰的方法。
challenge = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

def spiral_elements(array):
    while array:
        first_row, *rest = array
        yield from first
        array = tuple(reversed(tuple(zip(*rest))))

result = list(spiral_elements(challenge))
print(result)

# [1, 2, 3, 6, 9, 8, 7, 4, 5]
2
一种解决方案涉及到方向的指示，包括右、左、上、下和它们对应的限制（索引）。一旦第一行被打印出来，并且方向从右转向下时，通过增加上限来丢弃该行。一旦最后一列被打印出来，并且方向改变为左时，通过减少右边的限制来丢弃该列...详细信息可以在易于理解的C代码中看到。
#include <stdio.h>
#define N_ROWS 5
#define N_COLS 3

void print_spiral(int a[N_ROWS][N_COLS])
{
    enum {up, down, left, right} direction = right;
    int up_limit = 0,
        down_limit = N_ROWS - 1,
        left_limit = 0,
        right_limit = N_COLS - 1,
        downcount = N_ROWS * N_COLS,
        row = 0,
        col = 0;

    while(printf("%d ", a[row][col]) && --downcount)
        if(direction == right)
        {
            if(++col > right_limit)
            {
                --col;
                direction = down;
                ++up_limit;
                ++row;
            }
        }
        else if(direction == down)
        {
            if(++row > down_limit)
            {
                --row;
                direction = left;
                --right_limit;
                --col;
            }
        }
        else if(direction == left)
        {
            if(--col < left_limit)
            {
                ++col;
                direction = up;
                --down_limit;
                --row;
            }
        }
        else /* direction == up */
            if(--row < up_limit)
            {
                ++row;
                direction = right;
                ++left_limit;
                ++col;
            }
}

void main()
{
    int a[N_ROWS][N_COLS] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    print_spiral(a);
}

测试和下载链接

.

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接