Fork me on GitHub
0%

【LeetCode】54.Spiral-Matrix

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
例如,如果输入如下矩阵:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解题思路

比较直观的解法:
按照顺时针一圈一圈的打印,如何确定打印的圈数呢?

规律中可以发现圈数是跟矩阵的行列数是有关系的。
圈数 = min(行数,列数)/2 即:int circle = (min(row, col) +1) >> 1
然后按照四个步骤打印一圈:

  1. 从左到右打印一行
  2. 从上到下打印一列
  3. 从右到左打印一行
  4. 从下到上打印一列

比较特殊的例子:
这里写图片描述
最内一圈分别退化成只有两行、一列、一行,甚至可能只有一个数字。不论退化成什么,都至少需要执行第一步。
第三步要执行,固定的行,移动的列。至少需要两行两列,所以要满足此圈的终止行号大于起始行号并且终止列号大于起始列号 ,即row-i-1>i && c>=i
第四步要执行,则至少需要三行两列,所以要此圈满足的终止行号大于(起始行号+1)并且终止列号大于起始列号,即d>i && col-i-1 > i

54.spiral-matrix.cpplink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*=============================================================================
# Author: Hailin - https://fuhailin.github.io/
# Email: hailinfufu@outlook.com
# Description: /
=============================================================================*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> spiralOrder(vector<vector<int>> &matrix)
{
vector<int> result;
if (matrix.size() == 0)
return result;
int row = matrix.size();
int col = matrix[0].size();
int circle = (min(row, col) + 1) >> 1;
for (int i = 0; i < circle; i++)
{
//from left to right
for (int a = i; a < col - i; a++)
result.push_back(matrix[i][a]);
//from up to dowm
for (int b = i + 1; b < row - i; b++)
result.push_back(matrix[b][col - i - 1]);
//from right to left 终止列号>起始列号 && (终止行号) > 起始行号
for (int c = col - i - 2; (c >= i) && (row - i - 1 > i); c--) // 至少两行两列
result.push_back(matrix[row - i - 1][c]);
//from bottom to top 终止行号>起始行号+1&& 终止列号 > 起始列号
for (int d = row - i - 2; (d > i) && (col - i - 1 > i); d--) // 至少三行两列
result.push_back(matrix[d][i]);
}
return result;
}
int main()
{
int M, N;
cout << "The rows and columns of matrix" << endl;
cin >> M >> N;

vector<vector<int>> matrix(M, vector<int>(N));
vector<int> res;
/* input example
3 4
1 2 3 4
5 6 7 8
9 10 11 12
*/
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
cin >> matrix[i][j];
}
}
res = printMatrix(matrix);
for (int i = 0; i < res.size(); i++)
{
cout << res[i] << " ";
}

return 0;
}
Link
Send
Send
Pin
打赏一次,年薪百万.