Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.
array = [[1,2,3],
[4,5,6],
[7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]
For better understanding, please follow the numbers of the next array consecutively:
array = [[1,2,3],
[8,9,4],
[7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]
This image will illustrate things more clearly:
NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.
NOTE 2: The 0x0 (empty matrix) is represented as [[]]
请问下像这样的题目，有什么好的解题思路？
先mark一下，蛇形矩阵，一直没搞清楚算法。
我来贴一些排名较高的答案，真的要膜拜啊：
1：
snail = function(array) {
var result;
while (array.length) {
// Steal the first row.
result = (result ? result.concat(array.shift()) : array.shift());
// Steal the right items.
for (var i = 0; i < array.length; i++)
result.push(array[i].pop());
// Steal the bottom row.
result = result.concat((array.pop() || []).reverse());
// Steal the left items.
for (var i = array.length - 1; i >= 0; i--)
result.push(array[i].shift());
}
return result;
}
2：
snail = function(array) {
var res = [];
while(array.length) {
res = res.concat(array.shift())
array = expand(array);
}
return res;
}
function expand(matrix){
return matrix.reduce(function(res, arr, i){
arr.forEach(function(n, j){
if (!res[j]) res[j] = [];
res[j][i] = n;
})
return res;
}, []).reverse();
}
3：
snail = function(array) {
var maxx = array[0].length,
maxy = maxx,
minx = -1, miny = 0,
x = 0, y = 0,
result = [], dir = "r";
for(var i = maxx*maxx;i>0;i--){
result.push(array[y][x]);
switch (dir){
case "u": y--; break;
case "l": x--; break;
case "d": y++; break;
case "r": x++; break;
}
if(x==maxx-1 && y==miny){ dir="d"; minx++; }
else if(x==maxx-1 && y==maxy-1){ dir="l"; miny++; }
else if(x==minx && y==maxy-1){ dir="u"; maxx--; }
else if(x==minx && y==miny){ dir="r"; maxy--; }
}
return result;
}把走过的格子用一个二维数组标记下
用一个变量记录下当前的方向（初始方向是往右）,当当前的方向不能继续走的时候，改变方向至下一个方向，方向的顺序是右 下 左 上
然后根据方向的不同二维数组下标相应变化
譬如二维数组为map，某个元素可以用map[i][j]表示
右 map[i][j]变成map[i][j+1]
下 map[i][j]变成map[i+1][j]
左 map[i][j]变成map[i][j-1]
上 map[i][j]变成map[i-1][j]
模拟地走，定义一个方向数组，然后边界判断，改变方向，过程中哈希位置，我是这么干的
先沿边走一圈，获取剩余的2维数组后递归调用，一直到所有的数据都走完，退出递归，合并获取的结果
function snail(array){
var reusltArray=[],reusltArrayIndex=0;
var pp=[],temp;
var n=array.length;
if(n==0){
return [];
}
for(var i=0;i<n;i++){
if(i==0||i==n-1){
temp=array[i].slice(0,n);
if(i==n-1){
temp.reverse();
Array.prototype.splice.apply(pp,[n+i-1,temp.length].concat(temp));
}else{
Array.prototype.splice.apply(pp,[0,temp.length].concat(temp));
}
}else{
reusltArray[reusltArrayIndex++]=array[i].slice(1,n-1);
pp[n+i-1]=array[i][n-1];
pp[4*(n-1)-i]=array[i][0];
}
}
pp=pp.concat(snail(reusltArray));
return pp;
}a = [[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]];
snail(a);
function snail(a) {
find(0, a.length);
}
function find(s, e) {
for (var i = s; i < e; i++) {
document.write(a[s][i] + ",") ;
}
for (var i = s + 1; i < e; i++) {
document.write(a[i][e-1] + ",");
}
for (var i = e - 2; i >= s; i--) {
document.write(a[e-1][i] + ",");
}
if (s < e - 1) {
for (var i = e - 2; i >= s + 1; i--) {
document.write(a[i][s] + ",");
}
find (s+1, e-1);
} else {
return 0;
}
}