首页 > 代码库 > [LeetCode]54. Spiral Matrix

[LeetCode]54. Spiral Matrix

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].


题意:

根据给定的m*n矩阵。返回螺旋排序后的一维数组。

1  2  3
4  5  6
7  8  9
螺旋排序后的结果为:1,2,3,6,9,8,7,4,5
由此可知读取共分四个方向,而且是四个方向的轮回:
1)从左到右(横坐标不变,纵坐标逐步加一)。读取结果为:1 2 3
2)从上到下(纵坐标不变,横坐标逐步加matrixColSize)。读取结果为:6 9
3)从右往左(横坐标不变,纵坐标逐步减一)读取结果为:8 7
4)从下往上(纵坐标不变,横坐标逐步减matrixColSize)。读取结果为:4

定义brow代表从左到右执行的次数,erow代表从右到左执行的次数;bcol代表从下往上读取次数,ecol代表从上往下读取次数。所以有:
1)从左往右读取时,必须从bcol列开始读取,递增直到ecol列。
2)从右往左读取时,必须从ecol列开始读取,递减直到bcol列。
2)从上往下读取时,必须从brow行开始读取,递增直到erow行。
4)从下往上读取时,必须从erow行开始读取,递减直到brow行。



/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixRowSize, int matrixColSize)
{
    if ( !matrix )
    {
        return NULL;
    }
    
    int *dest = ( int *)malloc( sizeof(int) * matrixRowSize * matrixColSize + 1 );
    if ( !dest )
    {
        return NULL;
    }
    
    int times = 1;  
    int numbers = 0;
    
    int brow = 0;
    int erow = matrixRowSize - 1;
    int bcol = 0;
    int ecol = matrixColSize - 1;
    
    int index = 0;
    while ( numbers < matrixRowSize * matrixColSize )
    {
        if ( times % 4 == 1 )
        {
            int count = bcol;
            while ( count <= ecol )
            {
                *( dest + index ) = matrix[brow][count];
                count++;
                index++;
            }
            
            numbers = numbers + count - bcol;
            brow += 1;
        }
        else if ( times % 4 == 2 )
        {
            int count = brow;
            while ( count <= erow )
            {
                *( dest + index ) = matrix[count][ecol];
                count += 1;
                index++;
            }
            
            numbers = numbers + count - brow;
            ecol -= 1;
        }
        else if ( times % 4 == 3 )
        {
            int count = ecol;
            while ( count >= bcol )
            {
                *( dest + index ) = matrix[erow][count];
                count -= 1;
                index++;
            }
            
            numbers = numbers + ecol - count;
            erow -= 1;
        }
        else
        {
            int count = erow;
            while ( count >= brow )
            {
                *( dest + index ) = matrix[count][bcol];
                count -= 1;
                index++;
            }
            
            numbers = numbers + erow - count;
            bcol += 1;
        }
        times += 1;
        
    }
    *( dest + index ) = ‘\0‘;
    
    return dest;
}





[LeetCode]54. Spiral Matrix