二维数组的应用(沿对角线循环遍历)
给定一个大小为 m x n 的矩阵 mat,以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。
(返回结果为:[1, 2, 4, 7, 5, 3, 6, 8, 9])
思路:将遍历过程分为两组,偶数次向右上遍历,奇数次向左下遍历。
方式一
// 将遍历过程分为三部分(左、中、右)
// 行小于列
int[][] mat = {
{0, 1, 2, 0, 5},
{3, 4, 5, 2, 1},
{1, 3, 1, 5, 2}};
/*
向右上遍历:
左:counts[i] - j - 1, j
中:m - j - 1, n - counts[i] + j
右:m - j - 1, i - m + j + 1
向左下遍历
左:j, counts[i] - j - 1
中:m - counts[i] + j, n - j - 1
右:j, i - j
*/
// 行大于列
int[][] mat2 = {
{0, 1, 2},
{3, 4, 5},
{1, 3, 1},
{0, 5, 2},
{5, 2, 1}};
/*
向右上遍历:
左:counts[i] - j - 1, j
中:m - j - 1, n - counts[i] + j
右:i - j, j
向左下遍历
左:j, counts[i] - j - 1
中:m - counts[i] + j, n - j - 1
右:i - n + j + 1, n - j - 1
*/
代码实现:
public static int[] findDiagonalOrder(int[][] mat) {
if (mat.length == 0) {
return new int[0];
}
int m = mat.length; // 行数
int n = mat[0].length; // 列数
int[] result = new int[m * n]; // 存储结果
int time = m + n - 1; // 循环次数
int[] counts = new int[time]; // 每次循环遍历元素个数
int min = Math.min(m, n);
int index = 0; // 当前遍历数据的索引
for (int i = 0; i < time; i++) {
// 计算每次循环遍历元素个数
if (i < min) { // 左上部分
counts[i] = i + 1;
} else if (i >= time - min) { // 中间部分
counts[i] = time - i;
} else {
counts[i] = min; // 右下部分
}
// 向上遍历
if (i % 2 == 0) {
for (int j = 0; j < counts[i]; j++) {
if (i < min) {
result[index] = mat[counts[i] - j - 1][j];
} else if (i >= time - min) {
result[index] = mat[m - j - 1][n - counts[i] + j];
} else {
if (m <= n) { // 行数小于等于列数
result[index] = mat[m - j - 1][i - m + j + 1];
} else { // 行数大于列数
result[index] = mat[i - j][j];
}
}
index++;
}
} else {
// 向下遍历
for (int j = 0; j < counts[i]; j++) {
if (i < min) {
result[index] = mat[j][counts[i] - j - 1];
} else if (i >= time - min) {
result[index] = mat[m - counts[i] + j][n - j - 1];
} else {
if (m <= n) {
result[index] = mat[j][i - j];
} else {
result[index] = mat[i - n + j + 1][n - j - 1];
}
}
index++;
}
}
}
return result;
}
方式二
思路:利用图形观察出数学代数关系和规律。
代码实现:
public static int[] findDiagonalOrder2(int[][] matrix) {
if (matrix.length == 0) {
return new int[0];
}
int m = matrix.length;
int n = matrix[0].length;
int[] result = new int[m * n]; // 存放数组
int count = n + m - 1; // 对角线方向次数
int row = 0, col = 0, index = 0; // 定义初始化 行标记,列标记,存放数组索引
// 开始对角线循环
for (int i = 0; i < count; i++) {
//判断对角线方向:偶数右上,奇数左下
if (i % 2 == 0) {
// 右上操作
while (row >= 0 && col < n) {
result[index] = matrix[row][col]; // 将矩阵数存入存放数组
index++; // 索引后移
// 右上规律:行减一,列加一
row--;
col++;
}
// 判断是否为越界情况:不越界正常行加一,越界行加二,列减一
if (col < n) {
row++;
} else {
row += 2;
col--;
}
} else { // 左下操作:按规律与右上相反即可
while (row < m && col >= 0) {
result[index] = matrix[row][col];
index++;
row++;
col--;
}
if (row < m) {
col++;
} else {
row--;
col += 2;
}
}
}
return result;
}