题目要求
1
2
3
4
5
6
7
8
9
10
11
| 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].
|
按照顺时针方向旋转访问数组中的元素
思路一：按行遍历，array转化为list
因为List不允许跳跃插入，也就是说如果插入的index大于list的size，就会报出IndexOutOfBoundException。所以这里我打算采取int[]数组先存储值，再用Arrays.asList转化成list。
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
| public List<Integer> spiralOrder(int[][] matrix) {
int row = matrix.length;
if(row == 0){
return new ArrayList<Integer>();
}
int column = matrix[0].length;
Integer[] result = new Integer[row*column];
int prev = -1;
int tempRow = row;
int tempColumn = column;
for(int i = 0 ; tempRow>1&&tempColumn>1 ; i++){
for(int j = 0 ; j<tempColumn ; j++){
result[prev+j+1] = matrix[i][j+i];
result[prev+tempRow+tempColumn-1+tempColumn-j-1] = matrix[i+tempRow-1][j+i];
}
for(int j = 1 ; j<tempRow-1 ; j++){
result[prev+tempColumn+j] = matrix[j+i][column-i-1];
result[prev+tempColumn+tempRow+tempColumn-2+tempRow-j-1] = matrix[j+i][i];
}
prev += spiralCount(tempRow, tempColumn);
tempRow -=2;
tempColumn -=2;
}
if(tempRow == 1){
for(int i = 0 ; i<tempColumn ; i++){
result[prev+i+1] = matrix[row/2][row/2+i];
}
}
if(tempColumn == 1){
for(int i = 0 ; i<tempRow ; i++){
result[prev+i+1] = matrix[column/2+i][column/2];
}
}
return Arrays.asList(result);
}
private int spiralCount(int row, int column){
if(row<=1){
return column;
}else{
return (row+column)*2 - 4;
}
}
|
但是在这个方法中，先利用int[]在转化成List相当影响效率，虽说只需要遍历n/2个数组。
思路二：利用List顺序插入
为了避免类型转化带来的不必要的性能下降，最好直接利用List顺序插入，一次遍历int[][]数组。我们已知，除非特殊情况，每一圈必定都包含以下遍历，顺序的来说，就是从左往右遍历，再从上往下遍历，再从右往左遍历，再从下往上遍历。这时只需要从左往右遍历的下标和从上往下的下标依次记录了就行。
从左往右便利后，colBegin+1。从上往下遍历后，rowEnd-1。这时需要判断是否有往回遍历的需要。从右往左遍历后，colEnd-1。从下往上遍历后，rowBegin+1。
代码如下：
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
| public List<Integer> spiralOrder2(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if (matrix.length == 0) {
return res;
}
int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
for (int j = colBegin; j <= colEnd; j ++) {
res.add(matrix[rowBegin][j]);
}
rowBegin++;
for (int j = rowBegin; j <= rowEnd; j ++) {
res.add(matrix[j][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
for (int j = colEnd; j >= colBegin; j --) {
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;
if (colBegin <= colEnd) {
for (int j = rowEnd; j >= rowBegin; j --) {
res.add(matrix[j][colBegin]);
}
}
colBegin ++;
}
return res;
}
|