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

Spiral traversal of a matrix - recursive solution in JavaScript

提问by zahabba

I'm trying to come up with a solution that takes in a matrix like this:

我正在尝试提出一个采用这样的矩阵的解决方案：

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

and returns an array traversing the array as a spiral, so in this example: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

并返回一个以螺旋形式遍历数组的数组，因此在此示例中： [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

I'm having trouble getting this recursive solution to work, in which the result array takes the first array, the final elements of the rest of the arrays, the bottom array in reverse order, and then the first elements of the middle arrays, and then reforms the array without that outer "shell" so that it can be recursively called on what's left until there's an array of one element in the center or a 2x2 matrix (my base cases, although the latter might not be necessary...)

我无法让这个递归解决方案工作，其中结果数组采用第一个数组，其余数组的最后一个元素，底部数组以相反的顺序，然后是中间数组的第一个元素，以及然后在没有那个外部“外壳”的情况下重新构造数组，以便可以递归地调用剩下的数组，直到中心有一个元素的数组或 2x2 矩阵（我的基本情况，尽管后者可能不是必需的......）

My solution, which doesn't work, is as follows. Any suggestions on how I can make this work?

我的解决方案不起作用，如下所示。关于如何进行这项工作的任何建议？

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

采纳答案by Cymen

Your code is very close but it is doing more than it needs to do. Here I simplify and bug fix:

您的代码非常接近，但它做的比它需要做的要多。在这里，我进行了简化和错误修复：

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

Running it outputs:

运行它输出：

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

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

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

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

Important things:

重要的事：

• concaton Array returns the result -- it does not mutate the caller so you need to save the result of the concatlike so: result = result.concat(otherArray)
• check the terminating condition at top of recursive array
• for each pass, do the expected (top, right, bottom, left)
• return the result

• concaton Array 返回结果——它不会改变调用者，所以你需要保存concat类似的结果：result = result.concat(otherArray)
• 检查递归数组顶部的终止条件
• 对于每次通过，执行预期的（顶部，右侧，底部，左侧）
• 返回结果

Here is how I would do it but I would add error checking to verify the array has an equal number of "rows" and "columns". So assuming the input is valid, here we go:

这是我将如何做到的，但我会添加错误检查以验证数组具有相同数量的“行”和“列”。所以假设输入是有效的，我们开始：

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

Which outputs:

哪些输出：

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

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

The general idea is we know for each pass we need to do these things:

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

1. Add the first array in input
2. Add the last item from each remaining array in input
3. Add the last array in input
4. Add the first item from each remaining array in input

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

So if we do the recursion with doing that at each pass, we can accomplish the spiraling.

因此，如果我们在每次通过时进行递归，我们就可以完成螺旋上升。

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

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

回答by Lior Elrom

Spiral Array (ES6)

螺旋阵列 (ES6)

ES6 allows us to keep it simple:

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

回答by Nitish Narang

This solution is for any kind of matrix (m * n), not just square(m * m). Below example takes 5*4 matrix and prints in spiral format.

此解决方案适用于任何类型的矩阵 (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--;
}

回答by Bergi

Your algorithm seems fine, there is only one mistakeThere are a few things, some more hard to spot than others.

你的算法看起来不错，只有一个错误有几件事，有些比其他更难发现。

1. The concatmethoddoes not alter the array (like pushdoes), but returns a new array that contains all the elements from the original array and the arguments. The resultis not mutated.

   To fix this, you could either

   • use result = result.concat(…);
   • make it an explicit loop where you do result.push(…)(like the down, left and up ones you already wrote) or
   • use result.push.apply(result, …)to push multiple values at once
2. Your "left" or "up" loop does miss one element, the bottom left one. Either when going left, you need advance to the first element (use >= 0in the condition), or when going up you will need to start in the last instead of the second-to-last row (matrix.length-1)
3. In the loop that shrinks the matrix for the next iteration you forgot the last row, it needs to be for (var i=0; i < temp.length; i++)(not temp.length-1). Otherwise you get very unfortunate results.
4. Your base case should be 0 (and 1), not (1 and) 2. This will both simplify your script and avoid errors (in edge cases).
5. You expect your matrices to be square, but they could be rectangular (or even have lines of uneven length). The .lengthyou are accessing might be not the one you expect - better doublecheck and throw an error with a descriptive message.
6. Both spiralTraversaland goAroundare missing a returnstatement for the (recursive) call. They just fill up resultbut don't return anything.

1. 该concat方法不会改变数组（就像push那样），而是返回一个新数组，其中包含原始数组中的所有元素和参数。在result没有发生突变。

   要解决此问题，您可以

   • 利用 result = result.concat(…);
   • 使其成为您执行的显式循环result.push(…)（例如您已经编写的向下，向左和向上循环）或
   • 用于一次推送多个值result.push.apply(result, …)
2. 您的“左”或“上”循环确实错过了一个元素，即左下角的元素。向左时，您需要前进到第一个元素（>= 0在条件中使用），或者向上时，您需要从最后一行而不是倒数第二行开始 ( matrix.length-1)
3. 在为下一次迭代缩小矩阵的循环中，您忘记了最后一行，它需要是for (var i=0; i < temp.length; i++)(not temp.length-1)。否则你会得到非常不幸的结果。
4. 您的基本情况应该是 0（和 1），而不是（1 和）2。这将简化您的脚本并避免错误（在边缘情况下）。
5. 您希望矩阵是方形的，但它们也可能是矩形的（或者甚至是长度不均匀的线）。在.length您访问可能不是你所期望的一个-更好的双检，并抛出一个错误，用描述性的消息。
6. 这两个spiralTraversal和goAround缺少一个return针对（递归）调用语句。他们只是填满result但不返回任何东西。

回答by Artur Grigio

Recursive Solution:

递归解决方案：

Instead of going around, I just go over the top row, and the rightmost column, then recursively call the function on the "reversed" matrix.

我没有四处走动，而是越过顶行和最右边的列，然后递归调用“反转”矩阵上的函数。

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

let spiral = (mat) => {
    if(mat.length && mat[0].length) {
        mat[0].forEach(entry => { console.log(entry)})
        mat.shift();
        mat.forEach(item => {
            console.log(item.pop())
        });
        spiral(reverseMatrix(mat))
    }
    return;
}

let reverseMatrix = (mat) => { 
    mat.forEach(item => { 
        item.reverse() 
    }); 
    mat.reverse(); 
    return mat; 
}

console.log("Clockwise Order is:")
spiral(input)

回答by Eksa

Here my function :

这是我的功能：

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

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


function polaSpiral(array_masalah) {
    function spiral(array) {
        if (array.length == 1) {
        return array[0];
      }

        var firstRow    = array[0]
        , numRows     = array.length
        , nextMatrix  = []
        , newRow
        , rowIdx
        , colIdx      = array[1].length - 1

        for (colIdx; colIdx >= 0; colIdx--) {
        newRow = [];

        for (rowIdx = 1; rowIdx < numRows; rowIdx++) {
          newRow.push(array[rowIdx][colIdx]);
        }

        nextMatrix.push(newRow);
      }

        firstRow.push.apply(firstRow, spiral(nextMatrix));
        return firstRow
    }

    console.log(spiral(array_masalah));
}


polaSpiral(array_masalah) // [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
polaSpiral(array_masalah_2) // [ 1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12 ]

回答by ASHISH RANJAN

const spiralOrder = matrix => {
  if (!matrix || matrix.length === 0) {
    return [];
  }
  let startRow = 0;
  let startCol = 0;

  let ans = [];
  let endCol = matrix[0].length - 1;
  let endRow = matrix.length - 1;

  while (startRow <= endRow && startCol <= endCol) {
    for (let i = startCol; i <= endCol; i++) {
      ans.push(matrix[startRow][i]);
    }

    startRow++;

    for (let i = startRow; i <= endRow; i++) {
      ans.push(matrix[i][endCol]);
    }
    endCol--;

    if (startRow <= endRow) {
      for (let i = endCol; i >= startCol; i--) {
        ans.push(matrix[endRow][i]);
      }
      endRow--;
    }

    if (startCol <= endCol) {
      for (let i = endRow; i >= startRow; i--) {
        ans.push(matrix[i][startCol]);
      }
      startCol++;
    }
  }
  return ans;
};

let input = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
//Output: [1, 2, 3, 6, 9, 8, 7, 4, 5];
spiralOrder(input);

回答by Mike B

While not recursive, it at least outputs the correct answer of:

虽然不是递归的，但它至少会输出以下正确答案：

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

I'd say the only weird thing about this is having to "reset" the variables i,j after each while loop. Also, there's probably a cleaner recursive solution.

我想说唯一奇怪的事情是必须在每个 while 循环后“重置”变量 i,j。此外，可能有一个更清洁的递归解决方案。

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

function spiralTraversal(array) {
  let discovered = new Set();
  let result = [];  
  let totalSpots = array.length * array[0].length;
  let direction = 'right';

  for (var i = 0; i < array.length; i ++) {
    for (var j = 0; j < array[i].length; j++) {   

      while (totalSpots) {
        while (direction === 'right' && !!bounds(array, i, j) && !discovered.has(array[i][j])) {  
          discovered.add(array[i][j]);                        
          result.push(array[i][j]);
          totalSpots--;                            
          j++;                         

        }

        direction = 'down';  
        i++;
        j--;


        while (direction === 'down' && !!bounds(array,i, j) && !discovered.has(array[i][i])) {      
          discovered.add(array[i][j]);                    
          result.push(array[i][j]);
          totalSpots--;          
          i++;                                           
        }


        direction = 'left';  
        j--;
        i--;


        while (direction === 'left' && !!bounds(array, i, j) && !discovered.has(array[i][j])) {  
          discovered.add(array[i][j]);                    
          result.push(array[i][j]);
          totalSpots--;       
          j--;                         
        }


        direction = 'up';          
        i--;
        j++


        while (direction === 'up' && bounds(array, i, j) && !discovered.has(array[i][j])) {
          discovered.add(array[i][j]);          
          result.push(array[i][j]);
          totalSpots--;          
          i--;                                   
        }

        direction = 'right';        
        j++;
        i++;

      }          
    }
  }
  return result;
}

function bounds(array, i, j){
  if (i < array.length && i >= 0 && j < array[0].length && j >= 0) {
    return true;
  } else {
    return false;
  }
};

回答by Spangle

Below is a Javascript solution. I have added comments to the code so you can follow along with the process :)

下面是一个 Javascript 解决方案。我在代码中添加了注释，以便您可以按照流程进行操作:)

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

var n = array.length;

//create empty 2d array

var startRow = 0;
var endRow = n - 1;
var startColumn = 0;
var endColumn = n - 1
var newArray = [];

// While loop is used to spiral into the 2d array.
while(startRow <= endRow && startColumn <= endColumn) {

    // Reading top row, from left to right
    for(var i = startColumn; i <= endColumn; i++) {
        newArray.push(array[startColumn][i]);
    }
    startRow++; // Top row read.

    // Reading right column from top right to bottom right
    for(var i = startRow; i <= endRow; i++) {
        newArray.push(array[i][endColumn]);
    }
    endColumn--; // Right column read

    // Reading bottom row, from bottom right to bottom left
    for(var i = endColumn; i >= startColumn; i--) {
        newArray.push(array[endRow][i]);
    }
    endRow--; // Bottom row read

    // Reading left column, from bottom left to top left
    for(var i = endRow; i >= startRow; i--) {
        newArray.push(array[i][startColumn]);
    }
    startColumn++; // left column now read.

} // While loop will now spiral in the matrix.

console.log(newArray);

:)

:)

回答by Ghaith Daragmeh

This solution takes spiral arrayand converts it to Ordered Array.

此解决方案采用螺旋阵列并将其转换为Ordered Array。

It Sorts Spiral Matrix with the format of Top, Right, Bottom, Left.

它以顶部，右侧，底部，左侧的格式对螺旋矩阵进行排序。

const matrix = [
  [1, 2, 3, 4, 5],
  [16, 17, 18, 19, 6],
  [15, 24, 25, 20, 7],
  [14, 23, 22, 21, 8],
  [13, 12, 11, 10, 9],
];

function getOrderdMatrix(matrix, OrderdCorner) {
  // If the Matrix is 0 return the OrderdCorner
  if (matrix.length > 0) {

    //Pushes the top of the matrix to OrderdCorner array
    OrderdCorner.push(...matrix.shift());

    let left = [];
    /*Pushes right elements to the Orderdcorner array and
     Add the left elements to the left array */
    for (let i = 0; i < matrix.length; i++) {
      OrderdCorner.push(matrix[i][matrix[i].length - 1])
      matrix[i].pop(); //Remove Right element

      if (matrix[i].length > 0) {
        //Starts from the last element of the left corner 
        left.push(matrix[(matrix.length - 1) - i][0])
        matrix[(matrix.length - 1) - i].shift();
      }
    }

    /* If the array length is grater than 0 add the bottom
    to the OrderdCorner array */
    if (matrix.length > 0) {
      OrderdCorner.push(...matrix.pop().reverse());
    }
    //Ads the left array to the OrderdCorner array
    OrderdCorner.push(...left);

    return getOrderdMatrix(matrix, OrderdCorner);
  } else {
    return OrderdCorner
  }
}

console.log(getOrderdMatrix(matrix,[]));

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

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