矩阵的螺旋遍历 - JavaScript中的递归解决方案

Question

我正在尝试提出一个像这样的矩阵的解决方案:

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

我无法使这个递归解决方案工作,其中结果数组采用第一个数组,其余数组的最终元素,反向顺序的底部数组,然后是中间数组的第一个元素,以及然后在不使用外部"shell"的情况下对数组进行重构,以便可以递归调用它,直到中心有一个元素的数组或2x2矩阵(我的基本情况,尽管后者可能不是必需的......)

我的解决方案不起作用,如下所示.关于如何使这项工作的任何建议？

var spiralTraversal = function(matriks){
  var result = [];
    var goAround = function(matrix) {
        var len = matrix[0].length;
        if (len === 1) {
            result.concat(matrix[0]);
            return result;
        }
        if (len === 2) {
            result.concat(matrix[0]);
            result.push(matrix[1][1], matrix[1][0]);
            return result;
        }
        if (len > 2) {
            // right
            result.concat(matrix[0]);
            // down
            for (var j=1; j < matrix.length - 1; j++) {
                result.push(matrix[j][matrix.length -1]);
            }
            // left
            for (var l=matrix.length - 2; l > 0; l--) {
                result.push(matrix[matrix.length - 1][l]);
            }
            // up
            for (var k=matrix.length -2; k > 0; k--) {
                result.push(matrix[k][0]);
            }
        }
        // reset matrix for next loop
        var temp = matrix.slice();
        temp.shift();
        temp.pop();
        for (var i=0; i < temp.length - 1; i++) {
            temp[i] = temp[i].slice(1,-1);
        }
        goAround(temp);
    };
    goAround(matriks);  
};

Answer 1

螺旋阵列(ES6)

ES6允许我们保持简单:

function spiral(matrix) {
    const arr = [];

    while (matrix.length) {
        arr.push(
            ...matrix.shift(),
            ...matrix.map(a => a.pop()),
            ...matrix.pop().reverse(),
            ...matrix.map(a => a.shift()).reverse()
        );
    }
    return arr;
}

Answer 2

你的代码非常接近,但它的功能却超出了它的需要.这里我简化并修复错误:

var input = [[1,  2,   3,  4],
             [5,  6,   7,  8],
             [9,  10, 11, 12],
             [13, 14, 15, 16]];

var spiralTraversal = function(matriks){
  var result = [];
    var goAround = function(matrix) {
        if (matrix.length == 0) {
            return;
        }

        // right
        result = result.concat(matrix.shift());

        // down
        for (var j=1; j < matrix.length - 1; j++) {
            result.push(matrix[j].pop());
        }

        // bottom
        result = result.concat(matrix.pop().reverse());

        // up
        for (var k=matrix.length -2; k > 0; k--) {
            result.push(matrix[k].shift());
        }

        return goAround(matrix);
    };

    goAround(matriks);

    return result;
};
var result = spiralTraversal(input);

console.log('result', result);

运行它输出:

result [1, 2, 3, 4, 12, 16, 15, 14, 13, 5, 6, 7, 8, 11, 10, 9]

JSFiddle:http://jsfiddle.net/eb34fu5z/

重要的事情:

• concaton Array返回结果 - 它不会改变调用者,因此你需要保存concat类似的结果,这样:result = result.concat(otherArray)
• 检查递归数组顶部的终止条件
• 每次通过,做预期的(顶部,右侧,底部,左侧)
• 返回结果

这是我将如何做,但我会添加错误检查,以验证数组有相同数量的"行"和"列".所以假设输入有效,我们在这里:

var input = [[1,  2,   3,  4],
             [5,  6,   7,  8],
             [9,  10, 11, 12],
             [13, 14, 15, 16]];

function run(input, result) {
    if (input.length == 0) {
        return result;
    }

    // add the first row to result
    result = result.concat(input.shift());

    // add the last element of each remaining row
    input.forEach(function(rightEnd) {
        result.push(rightEnd.pop());
    });

    // add the last row in reverse order
    result = result.concat(input.pop().reverse());

    // add the first element in each remaining row (going upwards)
    var tmp = [];
    input.forEach(function(leftEnd) {    
        tmp.push(leftEnd.shift());
    });
    result = result.concat(tmp.reverse());

    return run(input, result);
}

var result = run(input, []);

console.log('result', result);

哪个输出:

result [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

一般的想法是我们知道每次通过我们需要做这些事情:

1. 在输入中添加第一个数组
2. 在输入中添加每个剩余数组中的最后一项
3. 在输入中添加最后一个数组
4. 在输入中添加每个剩余数组中的第一个项目

因此,如果我们在每次传递中执行递归操作,我们就可以完成螺旋式上升.

JSFiddle:http://jsfiddle.net/2v6k5uhd/

Answer 3

该解决方案适用于任何类型的矩阵(m*n),而不仅仅是方形(m*m).下面的例子采用5*4矩阵并以螺旋格式打印.

var matrix =  [[1,2,3,4], [14,15,16,5], [13,20,17,6], [12,19,18,7], [11,10,9,8]];

var row = currentRow = matrix.length, column = currentColumn = matrix[0].length;

while(currentRow > row/2 ){

  // traverse row forward
  for(var i = (column - currentColumn); i < currentColumn ; i++) { console.log(matrix[row - currentRow][i]); }

  // traverse column downward
  for(var i = (row - currentRow + 1); i < currentRow ; i++) { console.log(matrix[i][currentColumn - 1]) }

  // traverse row backward
  for(var i = currentColumn - 1; i > (column - currentColumn) ; i--) { console.log(matrix[currentRow - 1][i - 1]); }

  // traverse column upward
  for(var i = currentRow - 1; i > (row - currentRow + 1) ; i--) { console.log(matrix[i - 1][column - currentColumn]) }

  currentRow--;
  currentColumn--;
}