KK's blog

每天积累多一些

0%

LeetCode 054 Spiral Matrix

Posted on Edited on Disqus:

LeetCode 054 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].

题目大意：

给定一个mxn的矩阵（m行 n列），以螺旋状返回矩阵中的所有元素。

解题思路：

打印方法主要是以下两种：第一种四边对称打印，实现起来边际情况很多，不推荐。因为要不断向内遍历，所以对称打印不合适。第二种方法是每条边比上一条少一个，
用四个指针，top, bottom, left, right来记录四个边界，每打印完一条边该边界向内扩展。注意有些回路不是完整比如[1,2]或上面例子中5就不是完整回路，此情况，
注意判断top和bottom以及left和right关系即可。四指针法可以进一步升级到两指针法甚至一个指针法，其实都是大同小异。

注意事项：

  1. 注意不是所有矩阵都有完整回路。所以后两个for循环要加if语句
  2. 右边和左边，遍历矩阵用matrix[i][right]，而不是matrix[right][i]
  3. Python中从后往前遍历要注意始点-1，range(right, left - 1, -1):

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
	if not matrix or not matrix[0]:
		return []
	res = []
	top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			res.append(matrix[top][i])
		top += 1
		for i in range(top, bottom + 1):
			res.append(matrix[i][right])  # remember [i[[right] not [right][i]
		right -= 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				res.append(matrix[bottom][i])
			bottom -= 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				res.append(matrix[i][left])
			left += 1
	return res

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void spiral2(int[][] a){
	int rowTop = 0, rowBottom = a.length-1, colLeft = 0, colRight = a[0].length-1;
	
	while(rowTop<=rowBottom && colLeft<=colRight){
		//topRow
		for(int i=colLeft;i<=colRight;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=rowBottom;i++)
			System.out.print(a[i][colRight]+" ");
		colRight--;
		if(rowTop<=rowBottom){
			for(int i=colRight;i>=colLeft;i--)
				System.out.print(a[rowBottom][i]+" ");
			rowBottom--;
		}
		if(colLeft<=colRight){
			for(int i=rowBottom;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void spiral3(int[][] a){
	int rowTop = 0, colLeft = 0;
	
	while(rowTop<=a.length-rowTop-1 && colLeft<=a[0].length-colLeft-1){
		//topRow
		for(int i=colLeft;i<=a[0].length-colLeft-1;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=a.length-rowTop;i++)
			System.out.print(a[i][a[0].length-colLeft-1]+" ");
		//colRight--;
		if(rowTop<=a.length-rowTop){
			for(int i=a[0].length-colLeft-2;i>=colLeft;i--)
				System.out.print(a[a.length-rowTop][i]+" ");
		}
		if(colLeft<=a[0].length-colLeft-2){
			for(int i=a.length-rowTop-1;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void spiral4(int[][] a){
	int num = Math.min(a.length, a[0].length);
	for(int st=0;st<(num+1)/2;st++){
		//complete edge(top)
		for(int i=st;i<a[0].length-st;i++)
			System.out.print(a[st][i]+" ");
		//complete edge-top (right)
		for(int i=st+1;i<a.length-st;i++)
			System.out.print(a[i][a[0].length-1-st]+" ");
		if(a[0].length-2-st>st)
			for(int i=a[0].length-2-st;i>=st;i--)
				System.out.print(a[a.length-st-1][i]+" ");
		if(a.length-2-st>st+1)
			for(int i=a.length-2-st;i>=st+1;i--)
				System.out.print(a[i][st]+" ");
	}
}

算法分析：

时间复杂度为O(mn)，空间复杂度O(1)。

Free mock interview