二维数组
前面我们已经了解过一维数组了,然而在很多情况,我们需要用到多维数组,它更适合像表或者矩阵这样更复杂的结构。
重点解释二维数组如下问题:
- 二维数组在内存中是如何存放的?
- 如何运用二维数组来解决问题?
二维数组简介
二维数组是一种结构较为特殊的数组,只是将数组中的每个元素变为了一维数组。
所以二维数组的本质上仍然是一个一维数组,内部的一维数组仍然从索引 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; 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)); while(!q.empty()){ auto t = q.front(); q.pop(); for (int i = 0; i < row; i++) matrix[i][t.second] = 0; for (int j = 0; j < col; j++) matrix[t.first][j] = 0; } } };
|
官方给了一种解法我觉得很好,标记第一行元素的方式。在此记录一下:
- 遍历整个矩阵,如果 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) { 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 点就闭馆了。每次去图书馆都会让我对学习有着一种无与伦比的渴望,是一种发自心底的,想要努力的想法。那一刻不是为了什么目的,就好像触发了一种欲望,不同于渴了喝水、饿了吃饭的追求欲,更多的是一种精神上的满足。希望我可以记得这种感觉,因为我觉得它可以带给我想要的生活。
声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除。