Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

数组和字符串-03

二维数组

前面我们已经了解过一维数组了,然而在很多情况,我们需要用到多维数组,它更适合像表或者矩阵这样更复杂的结构。

重点解释二维数组如下问题:

  • 二维数组在内存中是如何存放的?
  • 如何运用二维数组来解决问题?

二维数组简介

二维数组是一种结构较为特殊的数组,只是将数组中的每个元素变为了一维数组。

所以二维数组的本质上仍然是一个一维数组,内部的一维数组仍然从索引 0 开始,我们可以将它看作一个矩阵,并处理矩阵的相关问题。

示例

类似一维数组,对于二维数组例如:A = [[1,2,3,4],[5,6,7,8],[1,3,5,7]],计算机同样会在内存中申请一段连续的空间,并记录第一行数组的索引位置,即 A[0][0]的内存地址,它的索引与内存地址关系如下图所示:

注意,实际数组中的元素由于类型的不同会占用不同的字节数,因此每个方格地址之间的差值可能不为 1。

实际题目中,往往使用二维数据处理矩阵类相关问题,包括矩阵旋转、对角线遍历,以及对子矩阵的操作等。

题目:旋转矩阵

给你一幅由 N×N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。
不占用额外内存空间能否做到?

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入:matrix =
[[1,2,3],
[4,5,6],
[7,8,9]],
输出:
[[7,4,1],
[8,5,2],
[9,6,3]]

输入:matrix =
[[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]],
输出:
[[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]]

个人理解
看到这个题,我首先是在纸上画了画,很直观的结果就是,将数组将数组列从后往前作为行的从前往后。那就 for 循环,交换下标位置即可(这种方法是错误的,因为旋转 90 度不是交换,所以必须先将 90 这个因素去掉。先将矩阵转置,就会发现,只需要翻转一下顺序即可)

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
if(matrix.size() == 0) return; // 特殊判定
int X = matrix[0].size(), Y = matrix.size(); // 获取到矩阵宽高
// 本来想直接交换的,结果不行,只能转置矩阵了
for(int i = Y-1; i >= 0; i--) for(int j = 0; j < i ; j++)
swap(matrix[i][j], matrix[j][i]);
// 对每行的元素进行翻转
for (int i = 0; i < Y; i++) for(int j = 0; j < X/2; j++)
swap(matrix[i][j], matrix[i][X-1-j]);
}
};

题目:零矩阵

编写一种算法,若 M×N 矩阵中某个元素为 0,则将其所在的行与列清零。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入:
[[1,1,1],
[1,0,1],
[1,1,1]]
输出:
[[1,0,1],
[0,0,0],
[1,0,1]]

输入:
[[0,1,2,0],
[3,4,5,2],
[1,3,1,5]]
输出:
[[0,0,0,0],
[0,4,5,0],
[0,3,1,0]]

个人理解
这个看起来比较简单,就是只要有 0,就把当前行列清零。比的就是怎么实现更优秀。
我们遍历整个矩阵,然后将 0 的坐标存下来,根据坐标来清零。

代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0) return;
// 定义行列,行列更好理解一些,省的X,Y,M,N乱七八糟的
int row = matrix.size(), col = matrix[0].size();
queue<pair<int,int>> q;
for(int i = 0; i < row; i++) for(int j = 0; j < col; j++)
if(!matrix[i][j]) q.push(make_pair(i,j)); // 遍历矩阵,将 0 的坐标推入
while(!q.empty()){
auto t = q.front();
q.pop();
for (int i = 0; i < row; i++) matrix[i][t.second] = 0; // y不变
for (int j = 0; j < col; j++) matrix[t.first][j] = 0; // x不变
}
}
};

官方给了一种解法我觉得很好,标记第一行元素的方式。在此记录一下:

  • 遍历整个矩阵,如果 cell[i][j]==0 就将第 i 行和第 j 列的第一个元素标记。
  • 第一行和第一列的标记是相同的,都是 cell[0][0],所以需要一个额外变量告知第一列是否被标记,同时用 cell[0][0]继续表示第一行的标记。
  • 然后,从第二行第二列的元素开始遍历,如果第 r 行或者第 c 列被标记了,那么就将 cell[r][c]设为 0。这里第一行和第一列的作用就相当于方法一中的 row_set 和 column_set。
  • 然后我们检查是否 cell[0][0]==0,如果是则赋值第一行的元素为零。
  • 然后检查第一列是否被标记,如果是则赋值第一列的元素为零。

代码如下(C++):

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
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0) return; // 特殊判定
const int row = matrix.size(), col = matrix[0].size(); // 定义行列
bool firstRow = false, firstCol = false; // 定义第一行列标记
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) { // 遍历判断是否为 0
if (i == 0) firstRow = true; // 第一行列特判
if (j == 0) firstCol = true;
matrix[0][j] = matrix[i][0] = 0; // 修改第一行列
}
}
}
for (int i = 1; i < row; i++) { // 遍历所有,修改
for (int j = 1; j < col; j++) {
if (!matrix[0][j] || !matrix[i][0]) matrix[i][j] = 0;
}
}
// 修改第一行和第一列
if (firstRow) for (int i = 0; i < col; i++) matrix[0][i] = 0;
if (firstCol) for (int i = 0; i < row; i++) matrix[i][0] = 0;
}
};

这样的时间复杂度为O(M×N),空间复杂的为O(1)

注意:在写的过程中,不想做第一行和第一列的标记,但是后来发现不太行。

看到很多人写的,速度很快,但是不知道为啥,复杂度都一样啊,迷~~~

题目:对角线遍历

给定一个含有 MxN 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

示例:

1
2
3
4
5
输入:
[[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]]
输出: [1,2,4,7,5,3,6,8,9]

说明:给定矩阵中的元素总数不会超过 100000 。

个人理解

先观察一下,对角线的话,坐标和是一样的并且按照线去递增,由此可以得出:

  • 坐标(x,y)相加的和是递增的
  • 每一条线上的坐标,都是 x++,y–(或者 y++,x–)
  • 相邻的每趟是反的

看是看懂了,不会写咋办 = ̄ ω  ̄=

参考别人的代码如下(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
if(matrix.size() == 0) return {}; // 特殊判定
int row = matrix.size(), col = matrix[0].size(); // 定义行列
vector<int> result;
for(int curveLine = 0; curveLine < row + col; curveLine++){ // 对角遍历
// 定义起止位置
int rowBegin = curveLine + 1 <= col ? 0 : curveLine + 1 - col;
int rowEnd = curveLine + 1 >= row ? row - 1 : curveLine;
if(curveLine % 2 == 1){ // 奇偶对角线方向反向
for(int i = rowBegin; i <= rowEnd; i++)
result.push_back(matrix[i][curveLine - i]);
}else{
for (int i = rowEnd ; i >= rowBegin; i--)
result.push_back(matrix[i][curveLine - i]);
}
}
return result;
};
};

今天去图书馆学习,由于疫情原因,下午 3 点就闭馆了。每次去图书馆都会让我对学习有着一种无与伦比的渴望,是一种发自心底的,想要努力的想法。那一刻不是为了什么目的,就好像触发了一种欲望,不同于渴了喝水、饿了吃饭的追求欲,更多的是一种精神上的满足。希望我可以记得这种感觉,因为我觉得它可以带给我想要的生活。

声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~