54. Spiral Matrix

妖狐艹你老母 2024-04-18 15:24 53阅读 0赞

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

Example 1:

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

Example 2:

Input:
    [
      [1, 2, 3, 4],
      [5, 6, 7, 8],
      [9,10,11,12]
    ]
    Output: [1,2,3,4,8,12,11,10,9,5,6,7]

题意：  
给定一个`m`行`n` 列的矩阵，返回这个矩阵的顺时针螺旋序的各个元素。  
即：从先顺时针遍历最外圈，再顺时针遍历此外圈···。

方法：  
显然，这就是一个模拟的问题了，跟着问题的要求实现一遍就行。  
但是在实现的过程中，需要注意以下 几点：

1.  顺时针的螺旋，先左->右，再上->下，再右->左，最后下到上。
2.  每旋转一圈，里面的半径就会变小，同一个位置的元素不能被遍历两次。

基于这两个观察，有两种实现方式：  
一、  
使用一个标识来标识，某个位置是否被访问过。当遍历的过，发现当前位置越界、或已经被遍历过了，那么就需要改变 遍历的方向。我们使用direct\[3\]=\{0,1,-1\} 表示 横竖方向的三种增量。

class Solution { 
    public:
    	struct _node
    	{ 
    		int x, y;
    		bool operator <(const _node & rh) const{ 
    			return x < rh.x || (x == rh.x && y < rh.y);
    		}
    	};
    	vector<int> spiralOrder(vector<vector<int>>& matrix) { 
    
    		vector<int> rst;
    		int m = matrix.size(), n = 0;
    		if (m > 0)
    		{ 
    			n = matrix[0].size();
    		}
    		int x = 0, y = 0;
    		_node node = {  x, y };
    		set<_node>  flags;
    		int xd = 1, yd = 0;
    		int direct[3] = {  0, 1, -1 };
    		while (rst.size() < m*n)
    		{ 
    			if (flags.find({ y,x}) == flags.end() && (x < n) && y < m && y >= 0 && x >= 0)
    			//说明目前的增长方向是合理的
    			{ 
    				rst.push_back(matrix[y][x]);
    				flags.insert({  y,x });
    			}
    			else
    			//目前增长方向需要变更
    			{ 
    				x -= xd;//取消之前的一步增长
    				y -= yd;//取消之前的一步增长
    				xd = yd = 0;
    				for (int j = 0; j < 3; j++)
    				//首先尝试变更 横轴
    				{ 
    					xd = direct[j];
    					if (flags.find({  y , x + xd }) == flags.end() && y < m && (x + xd) < n && y >= 0 && (x + xd) >= 0)
    					{ 
    						goto label;
    					}
    				}
    				xd = 0;
    				for (int j = 0; j < 3; j++)
    				//其次考虑变更纵轴
    				{ 
    					yd = direct[j];
    					if (flags.find({  y + yd, x  }) == flags.end() && (y + yd) < m && (x) < n && (y + yd) >= 0 && (x ) >= 0)
    					{ 
    						goto label;
    					}
    				}
    				yd = 0;
    				break;//无法再进行下去，说明整个矩阵已经遍历完全。
    			}
    			label:
    			x += xd;
    			y += yd;
    		}
    		return rst;
    	}
    };

二、  
使用 4个变量来维护上，下、左、右 已经遍历的顶部行、头部行、左列、右列。

class Solution { 
    public:
    	vector<int> spiralOrder(vector<vector<int>>& matrix) { 
    
    		vector<int> rst;
    		int m = matrix.size(), n = 0;// MxN
    		if (m > 0)
    		{ 
    			n = matrix[0].size();
    		}
    		int x = 0, y = 0;
    		int left = 0, right = n - 1, top = 0, bottom = m - 1;
    		int direction = 0;
    		while (rst.size()<m*n)
    		{ 
    			if (direction == 0)
    			{ 
    				for (int i = left; i <= right; i++)
    				{ 
    					rst.push_back(matrix[x][i]);
    				}
    				top++;//遍历了顶部
    				y=right;
    			}
    			else if (direction == 1)
    			{ 
    				for (int i = top; i <= bottom; i++)
    				{ 
    					rst.push_back(matrix[i][y]);
    				}
    				right--;//遍历了右列
    				x=bottom;
    			}
    			else  if (direction == 2)
    			{ 
    				for (int i = right; i >= left; i--)
    				{ 
    					rst.push_back(matrix[x][i]);
    				}
    				bottom--;//遍历的底部
    				y=left;
    			}
    			else if(direction == 3)
    			{ 
    				for (int i = bottom; i >= top; i--)
    				{ 
    					rst.push_back(matrix[i][y]);
    				}
    				left++;//遍历了左列
    				x=top;
    			}
    			direction = (direction + 1 ) % 4;
    		}
    		return rst;
    	}
    };

这种方法，空间复杂度低为O(1),但是时间复杂度类似。