logo标签列表

如何以螺旋模式遍历二维数组，并使用单个循环？

arraysalgorithmmatrixmultidimensional-arraycycle
4
给定一个二维数组，我想以螺旋方式遍历它并使用单个循环打印元素。例如，如果给定的数组是：
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34

该程序应该打印出以下内容：
10 15 20 25 30 31 32 33 34 29 24 19 14 13 12 11 16 21 26 27 28 23 18 17 22

从左上角开始，到达数组中心。
内存消耗/复杂度有任何限制吗？ - Prateek Jain
这个有帮助吗？http://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/。他们在O(mn)的复杂度下实现了它。 - Michiel uit het Broek
没有内存或运行时间的限制，但只能使用单个周期。 - Róbert Nagy
4个回答
4
以下是只用一个for循环的解决方案：

仅适用于矩阵满足n >= m的情况。

#include <iostream>

using namespace std;

int main()
{
//    int arr[4][3] = {{0, 9, 8} , {1, 10 , 7} , {2, 11, 6} , {3, 4, 5}};
//    int n = 4, m = 3;

    int arr[4][4] = {{0, 11, 10, 9} , {1, 12, 15, 8} , {2, 13, 14, 7} , {3, 4, 5, 6}};
    int n = 4, m = 4;

    int row = 0, col = 0, turn = 0;
    bool isTop = true;

    for(int nrElem = 0; nrElem <= (n*m); nrElem++)
    {
        //This part make the left, bottom, right part ( U form )
        if((row < n-1-turn) && (col != m-1) && (isTop == true))
        {
            cout << " " << arr[row][col];
            row++;
        } else {
            if((row == n-1-turn) && (col < m-1-turn))
            {
                cout << " " << arr[row][col];
                col++;
            } else {
                if((col == m-1-turn) && (row > 0))
                {
                    cout << " " << arr[row][col];
                    row--;
                } else {
                    isTop = false;
                }
            }
        }
        //

        //And this do the top backward parsing
        if((col > 0) && (isTop == false))
        {
            cout << " " << arr[row][col];
            col--;
        } else {
            if (isTop == false)
            {
                isTop = true;
                turn++;
                row += turn;
                col += turn;
            }
        }
    }

    cout << endl;
    return 0;
}
2
我们可以在单个周期内完成，而无需存储额外的矩阵。下面的代码假设您可以使用C++11中的std::vector，并基于geeks for geeks的示例。当然，该算法也可以不使用std::vector。此外，这只蜗牛按顺时针方向行进，作为练习，您应该将其改为逆时针 :). [我没有编译代码] 
#include <iostream>
#include <vector>

using namespace std;

void printSnail(vector<vector<int>> const &matrix)
{
  size_t nRow = matrix.size();       // Number of rows that are not printed yet
  size_t nCol = matrix[0].size();    // Number of columns that are not printed yet

  size_t k = 0;
  size_t l = 0;

  // Print all elements in the matrix
  while (k < nRow and l < nCol)
  {
    // Print first row of remaining rows
    for (size_t idx = l; idx < nCol; ++idx)
      cout << matrix[k][idx] << ' ';
    ++k;

    // Print last column of remaining columns
    for (size_t idx = k; idx < nRow; ++idx)
      cout << matrix[idx][nCol - 1] << ' ';
    --nCol;

    // Print last row of remaining rows
    if (k < nRow)
    {
      for (size_t idx = nCol - 1; idx >= l; --idx)
        cout << matrix[nRow - 1][idx] << ' ';
      --nRow;
    }

    // Print the first column of the remaining columns
    if (l < nCol)
    {
      for (size_t idx = nRow - 1; idx >= k; --idx)
        cout << matrix[idx][l] << ' ';
      ++l;
    }
  }
}
1
以下是如何在Javascript中实现它的方法。
snail = function(arr) {
    let [y, x] = [0, 0];
    let [rs, ls, us, ds] = [0, 0, 0, 0]
    let [xLimit, yLimit] = [arr.length, arr.length];
    let dir = 'right'
    const res = []
    const len = arr[0].length * arr[0].length
    const rowLen = arr[0].length
    while (res.length < len) {
        res.push(arr[y][x])
        switch (dir) {
            case 'right':
                if (x + 1 < xLimit) {
                    x++
                } else {
                    dir = 'down'
                    yLimit = rowLen - ds
                    rs++
                    y++
                }
                break;
            case 'down':
                if (y + 1 < yLimit) {
                    y++
                } else {
                    dir = 'left'
                    xLimit = ls
                    ds++
                    x--
                }
                break;
            case 'left':
                if (x > xLimit) {
                    x--
                } else {
                    dir = 'up'
                    yLimit = ds
                    ls++
                    y--
                }
                break;
            case 'up':
                if (y > yLimit) {
                    y--
                } else {
                    dir = 'right'
                    xLimit = rowLen - rs
                    us++
                    x++
                }
                break;
            default:
                break;
        }

    }
    return res
}

它不使用任何内置的Javascript函数，因此可以翻译成任何语言。

0
这里是您问题的简单解决方案：

  • 保持一个大小相同（所有单元格初始化为0）的2D数组（checkIfVisited），以便跟踪已经访问过的单元格。如果(i,j)为1，则表示原始单元格已经被访问过。

  • 我们借助于dir变量，在螺旋方式下遍历整个数组。

  • dir= 0 表示向下移动，1 表示向右移动，2 表示向上移动，3 表示向左移动。

  • 当i和j超出限制或要遍历的下一个单元格已经通过从checkIfVisited数组进行查找而被遍历时，我们改变方向。

我有一个上述算法的简单C++实现：

#include <iostream>
using namespace std;
int main() 
{
    int arr[5][5] = {10, 11, 12, 13, 14,
                     15, 16, 17, 18, 19,
                     20, 21, 22, 23, 24,
                     25, 26, 27, 28, 29,
                     30, 31, 32, 33, 34};

    int checkIfVisited[5][5] = {0,0,0,0,0,
                                0,0,0,0,0,
                                0,0,0,0,0,
                                0,0,0,0,0,
                                0,0,0,0,0};
    int i,j,dir,countVisited;
    dir = 0;
    countVisited = 0;
    i = 0;
    j = 0;
    while(countVisited<5*5)
    {
        cout<<arr[i][j]<<" ";
        checkIfVisited[i][j]=1;
        if(dir==0)
        {
            countVisited++;
            if(i+1>4 || checkIfVisited[i+1][j]==1){
                dir=1;
                j++;
            }
            else
                i++;
        }
        else if(dir==1)
        {
            countVisited++;
            if(j+1>4 || checkIfVisited[i][j+1]==1){
                dir=2;
                i--;
            }
            else
                j++;
        }
        else if(dir==2)
        {
            countVisited++;
            if(i-1<0 || checkIfVisited[i-1][j]==1){
                dir=3;
                j--;
            }
            else
                i--;
        }
        else
        {
            countVisited++;
            if(j-1<0 || checkIfVisited[i][j-1]==1){
                dir=0;
                i++;
            }
            else
                j--;
        }
    }

    return 0;
}

输出： 10 15 20 25 30 31 32 33 34 29 24 19 14 13 12 11 16 21 26 27 28 23 18 17 22

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接