遍历二维数组最外圈,要优雅.

Question

[1,2,3]
[4,5,6]
[7,8,9]

遍历二维数组最外圈 --> 12369874
我以前在算法书上看到一个很清晰明了的.想不起来了.

Answer 1

/**
 * @param {number[][]}
 * @return {number[]}
 */
var getOuter = function(the2dArr) {
    var result = [];
    var i = j = 0;
    var m = the2dArr.length;
    var n = the2dArr[1].length;
    for(; j < n; j++){
        result.push(the2dArr[i][j]);
    }
    for(j--, ++i; i < m; i++){
        result.push(the2dArr[i][j]);
    }
    for(i--, --j; j >= 0; j--){
        result.push(the2dArr[i][j]);
    }
    for(j++, --i; i > 0; i--){
        result.push(the2dArr[i][j]);
    }
    return result;
};

Answer 2

通过一些计算可以把4个循环变成1个循环+循环内判断

function goAround(arr) {
  var i=0,
    x = arr[0].length,
    y = arr.length,
    max = (x + y) * 2 - 4;//周长

  for(i = 0; i < max; i++) {
    if(i < x + y - 1) {
      //前半圈, i超过x-1的时候转弯
      visit(i - x + 1, i);
    } else {
      //后半圈，用max减比较容易理解，拐点在max - y + 1
      visit(max - i, max - y + 1 - i);
    }
  }

  function visit(a, b) {
    //越界统一处理
    a = limit(a, 0, y - 1);
    b = limit(b, 0, x - 1);
    console.log(`now at [${a}, ${b}], value = ${arr[a][b]}`);
  }

  //确保x在min~max之间
  function limit(x, min, max) {
    return x < min ? min
      : x > max ? max 
      : x;
  }
}

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

Answer 3

将遍历过程想象成一个质点沿着矩形的四条边在运动。

假设二维数组为arr。

# 运动方向矢量数组
VECTORS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

# 行、列
ROWS, COLS = len(arr), len(arr[0])

＃ 计数器
d, m, n = 0, 0, 0

while True:
    # 遍历
    print(arr[m, n])
    
    m2, n2 = m + VECTORS[d][0], n + VECTORS[d][1]
    
    # 判断是否要变向
    if m2 >= ROWS or m2 < 0 or n2 >= COLS or n2 < 0:
        d = d + 1

    m, n = m + VECTORS[d][0], n + VECTORS[d][1]
    
    if (m, n) == (0, 0):
        break

Answer 4

[1,2,3]
[4,5,6]
[7,8,9]

上面的数组比较特殊，其行列数是一致的。
现在用一个不一致的来说明

[1,2,3,4]
[5,6,7,8]
[9,A,B,C]

虽然这是一个二维数组，在C/C++中但是其实质还是一个一维的。
[1,2,3,4,5,6,7,8,9,A,B,C]
现在来看遍历的过程(下面图中第四步最后的括号中应该是“行数-2”)

写成C代码的形式

// 这里假设数据为整形，有row行，col列
#include <stdio.h>

void traverse(const int **arr,int row,int col)
{
    const int* data = (const int*)arr;
    int i = 0,step = 1;
    do{
        printf("%d,",data[i]);
        i+=step;
        if(i== col-1){
            step = col;    // 第二步，步长改为列数
        }
        else if(i == (col*row -1)){
            step = -1;    // 第三步，步长改为-1
        }
        else if(i == (col *(row-1))){
            step = -col;  // 第四步，步长改为负的列数
        }
    }while(i);
}

int main() {
    // 测试一下
    int arr[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    traverse((const int**)arr,3,4);
    return 0;
}

Answer 5

a[r][c]
a[0][c]+a[1][c]+a[1][0]+...+a[r][c]?

Answer 6

Python 3 代碼:

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

for e in a[0]:
    print(e)
for e in (row[-1] for row in a[1:-1]):
    print(e)
for e in reversed(a[-1]):
    print(e)
for e in (row[0] for row in a[-2:0:-1]):
    print(e)

不知道算不算優雅...

簡單來說就是就四個步驟：

1. 正走 first row

2. 正走 last col

3. 逆走 last row

4. 逆走 first col

只是要小心走過的不要再走(boundary condition)

Answer 7

(()=> {
    var matrix = (arr)=> {
        return Array.isArray(arr) ? [].concat.apply([], [arr.shift(), arr.pop()].concat(arr.map(item=>matrix(item)))) : [];
    };
    var demo = [
        [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, 26, 27, 28, 29, 30, 31]
    ];

    console.log(matrix(demo));
})();

没做结果按顺时针排序

Answer 8

不优雅的来一发。

function wtf(arr) {
  var index = 0, 
      length = arr.length,
      result = [];
  while (true) {
    var item = arr[Math.abs(index)];
    if (index === 0) {
        result = result.concat(item);
    } else if (index == length - 1) {
      index = -index;
      result = result.concat(item.reverse());
    } else {
      var i = index >= 0 ? item.length - 1 : 0;
      result.push(item[i]);
    }
    if (index === -1) {
      break;
    }
    index++;
  }
  return result;
}

Answer 9

数组确定一下遍历的方向顺序，然后用循环来变向。

应该算是优雅了吧 0 0

/**
 * @author +7w
 */
#include <stdio.h>

#include <vector>

typedef std::vector<std::vector<int> > VVI;

void travel(const VVI& a)
{
  static int dx[] = {0, 1, 0, -1};
  static int dy[] = {1, 0, -1, 0};

  int n = a.size();
  int m = a[0].size();

  auto checkin = [n, m](int x, int y) -> bool
  {
    return (0 <= x && x < n && 0 <= y && y < m);
  };

  for (int d = 0; d < 4; ++d) {
    static int x = 0, y = 0;
    for (; checkin(x + dx[d], y + dy[d]); x += dx[d], y += dy[d])
      printf("%d ", a[x][y]);
  }
  printf("\n");
}

int main()
{
  VVI a {{11, 12, 13, 14}, {21, 22, 23, 24}, {31, 32, 33, 34}};
  travel(a); // 11 12 13 14 24 34 33 32 31 21
  return 0;
}