注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex54 Spiral Matrix  

2015-05-16 21:39:01|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
顺时针读取矩阵

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

这个题严格来说和ex 48 rotate image几乎是一样的,甚至还简单一些。只不过需要找一下一次循环中的起点和终点。
另外还需要注意下min(m,n)中奇数和偶数的问题,因为有的遍历无法构成一次循环。
第二层循环的四个起点分别是
第一个坐标是(i,i)
第二个坐标是(i,n-1-i)
第三个坐标是(m-1-i,n-1-i)
第四个坐标是(m-1-i,i)
有了这四个基准,后面的循环就好做了。
见c代码

int* spiralOrder(int** matrix, int matrixRowSize, int matrixColSize) {

int m = matrixRowSize;
int n = matrixColSize;
int i, j, k,p;

int min = (m>n ? n : m);
int len;
if (min % 2 == 0)
{
len = (min) / 2;
}
else
{
len = (min) / 2;
len++;
}

int index = 0;
if (n <= 0 || m <= 0)
return NULL;
int *result = (int*)malloc(m*n*sizeof(int));
if (m == 1)
{
memcpy(result,matrix[0],n*sizeof(int));
return result;
}
if (n == 1)
{

for (i = 0; i < m; i++)
{
result[i] = matrix[i][0];
}
return result;
}
int start,end;
for (k = 0; k <len; k++)
{
i = k;
//第一个坐标是(i,i)
start = i;
end = n - 1 - i;
for (j = i; j < n-1-i; j++)
{
result[index] = matrix[i][j];
index++;
}
if ((index + 1) >= m*n)
{
//如果是奇数话,读到这里就结束了
result[index] = matrix[i][ n - 1 - i];
index++;
break;
}

//第二个坐标是(i,n-1-i)

start = i;
end = m - 1 - i;
j = n - 1 - i;
for (p = i; p < m-1-i; p++)
{
result[index] = matrix[p][j];
index++;
}

//第三个坐标是(m-1-i,n-1-i)
start = n - 1 - i;
end = i;
p = m - 1 - i;
for (j = n - 1 - i; j > i; j--)
{
result[index] = matrix[p][j];
index++;
}
//第四个坐标是(m-1-i,i)
start = m - 1 - i;
end = i;
j = i;
for (p = m - 1 - i; p > i; p--)
{
result[index] = matrix[p][j];
index++;
}
if (index >= m*n)
break;
}
printf("%d \n",index);
return result;
}


update java version with neat code 2015/12/4

import java.util.ArrayList;
import java.util.List;
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
return helper(matrix);
}
private List<Integer> helper(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0) {
return res;
}
int[] nx = {0, 1, 0, -1};
int[] ny = {1, 0, -1, 0};
int x = 0, y = -1; // 因为是从(0, 0) 开始的
int m = matrix.length, n = matrix[0].length;
int i = 0, k = 0;
while (m > 0 && n > 0) {
if (i % 2 == 0) {
k = n; // 走的行
m--; // 少了一行
} else {
k = m; // 走的列
n--; // 少了一列
}
while (k > 0) {
x += nx[i];
y += ny[i];
res.add(matrix[x][y]);
k--;
}
i++;
i %= 4;
}
return res;
}
}


  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017