[1,2,3]
[4,5,6]
[7,8,9]
遍历二维数组最外圈 --> 12369874
我以前在算法书上看到一个很清晰明了的.想不起来了.
a[r][c]
a[0][c]+a[1][c]+a[1][0]+...+a[r][c]?
数组确定一下遍历的方向顺序,然后用循环来变向。
应该算是优雅了吧 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;
}
不优雅的来一发。
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;
}
通过一些计算可以把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]
]);
[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;
}
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)
不知道算不算優雅...
簡單來說就是就四個步驟:
正走 first row
正走 last col
逆走 last row
逆走 first col
只是要小心走過的不要再走(boundary condition)
将遍历过程想象成一个质点沿着矩形的四条边在运动。
假设二维数组为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
(()=> {
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));
})();
没做结果按顺时针排序
/**
* @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;
};