javascript - js 二维数组循环遍历

Question

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

请问下像这样的题目，有什么好的解题思路？

Answer 1

把走过的格子用一个二维数组标记下
用一个变量记录下当前的方向（初始方向是往右）,当当前的方向不能继续走的时候，改变方向至下一个方向，方向的顺序是右 下 左 上
然后根据方向的不同二维数组下标相应变化

譬如二维数组为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]

Answer 2

我来贴一些排名较高的答案，真的要膜拜啊：
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;
}

Answer 3

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;
    }
 }

Answer 4

先mark一下，蛇形矩阵，一直没搞清楚算法。

Answer 5

模拟地走，定义一个方向数组，然后边界判断，改变方向，过程中哈希位置，我是这么干的

Answer 6

先沿边走一圈，获取剩余的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;

}