剑指Offer:顺时针打印矩阵

题目

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 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.

分析

这道题没有涉及复杂的数据结构或者高级的算法,主要考察的就是对数组和边界条件的控制能力。

由于是以外圈到内圈依次打印的,所以我们可以把矩阵想象成若干个圈,每次打印矩阵的一个圈。

我们把打印一圈分为四步:第一步,从左到右打印一行。第二步,从上到下打印一列。第三步,从右到左打印一行。最后,从下到上打印一列。

IMG_20180515_084814.jpg

需要注意的是,矩阵的最后一圈可能会退化,因此在打印这一圈的时候可能不在需要四步。

IMG_20180515_084805.jpg

通过分析我们可以发现,第一步总是需要的,因为打印一圈至少有一步。如果只有一行那就不需要第二步了,也就是需要第二步的前提条件是终止行号大于起始行号。需要第三步的前提条件是圈内至少有两行两列,也就是说,除了要求终止行号大于起始行号,还要求终止列号大于起始列号。同理需要第四步的前提条件是至少有三行两列,因此需要终止行号比起始行号至少大2,同时终止列号大于起始列号。

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
import java.util.ArrayList;
public class Solution {
public static void print(int [][] matrix,int top, int bottom, int left, int right, ArrayList result){
while (left <= right && top <= bottom){
for (int i = left; i <= right; i ++){
// System.out.println(matrix[top][i]+"-----");
result.add(matrix[top][i]);
}

if (top < bottom) {
for (int i = top+1; i <= bottom; i ++){
// System.out.println(matrix[i][right]+"-----");
result.add(matrix[i][right]);
}
}

if (bottom > top && left < right) {
for (int i = right-1; i >= left; i --){
// System.out.println(matrix[bottom][i]+"-----");
result.add(matrix[bottom][i]);
}
}

if (top < bottom-1 && left < right) {
for (int i = bottom-1; i > top; i --){
// System.out.println(matrix[i][left]+"-----");
result.add(matrix[i][left]);
}
}

left ++; top ++; right --; bottom --;
}
}

public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> result = new ArrayList<>();
int length = matrix.length;
if (matrix == null || length <= 0)
return result;
int bottom = length-1;
int right = matrix[0].length-1;
int top = 0;
int left = 0;
print(matrix,top,bottom,left,right,result);
return result;
}
}
请我一杯酸奶?
------ 本文结束感谢您的阅读-------------
0%