- 0. Leetcode [1351. 统计有序矩阵中的负数](https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/)
- 分析与解答
- 1. Leetcode [1672. 最富有客户的资产总量](https://leetcode.cn/problems/richest-customer-wealth/)
- 分析与解答
- 2. Leetcode [832. 翻转图像](https://leetcode.cn/problems/flipping-an-image/)
- 分析与解答
- 3. Leetcode [1329. 将矩阵按对角线排序](https://leetcode.cn/problems/sort-the-matrix-diagonally/)
- 分析与解答
- 总结
分析与解答给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。
解法1
遍历矩阵，计算满足条件的元素数量
class Solution {
public:
int countNegatives(vector>& grid) {
int m = grid.size(); // 行数
int n = grid[0].size(); // 列数
int result(0);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] < 0) {
result += 1;
}
}
}
return result;
}
};
该方法没有利用已有条件，直接遍历矩阵，算法时间复杂度为
O
(
m
n
)
O(mn)
O(mn)，其中
m
,
n
m,n
m,n 为矩阵的行数与列数
解法2
由于矩阵行列均为非递增，因此可以逆序查找，减少时间复杂度。对行从后向前查找，对列从前向后查找，若位置 grid[i, j] > 0，由列元素的非递增性可知，grid[i-1, j] > 0，即对第 i - 1 行，查找时的列表记可从第 i 行中满足 grid[i, j] < 0 的最小 j 开始：
class Solution {
public:
int countNegatives(vector>& grid) {
int m = grid.size(); // 行数
int n = grid[0].size(); // 列数
int result(0), k(0);
// 利用元素非递增的特性，m 从下往上扫描，n 从前往后扫描
for (int i = m - 1; i >= 0; --i) {
for (int j = k; j < n; ++j) {
if (grid[i][j] < 0) { // 找到当前行第一个小于 0 的元素，后续元素均小于 0
result += n - k;
break;
} else {
k++;
}
}
}
return result;
}
};
由于复用了上一次搜索的列号，因此复杂度为 O ( m + n ) O(m+n) O(m+n)
1. Leetcode 1672. 最富有客户的资产总量当然，在查找时也可以用二分法，加快搜索当前行元素的速度
分析与解答给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。
客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
根据题意，求矩阵的最大行和即可。遍历矩阵每一行，对改行元素求和，记录最大值：
class Solution {
public:
int maximumWealth(vector>& accounts) {
int result(0);
for (int i = 0; i < accounts.size(); ++i) {
int cur(0);
for (int j = 0; j < accounts[i].size(); ++j) { // 求第 i 行的元素和
cur += accounts[i][j];
}
if (result < cur) { // 更新最大行和
result = cur;
}
}
return result;
}
};
算法时间复杂度为 O ( m n ) O(mn) O(mn)
2. Leetcode 832. 翻转图像分析与解答给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。
例如，水平翻转 [1,1,0] 的结果是 [0,1,1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。
例如，反转 [0,1,1] 的结果是 [1,0,0]。
依题意，遍历每一行，将每列中位置为 [ i , j ] [i,j] [i,j] 的元素与位置为 [ i , n − j − 1 ] [i, n - j - 1] [i,n−j−1] 的元素交换即可，其中 n n n 为矩阵列数：
class Solution {
public:
vector> flipAndInvertImage(vector>& image) {
vector> result;
int r = image.size();
int c = image[0].size();
result.resize(r);
for (int i = 0; i < r; ++i) {
result[i].resize(c);
}
for (int i = 0; i < r; ++i) { // 遍历每一行
for (int j = 0; j < c / 2 + 1; ++j) { // 只需遍历一半列下标即可
result[i][j] = !image[i][c - 1 - j];
result[i][c - 1 - j] = !image[i][j];
}
}
return result;
}
};
算法时间复杂度为 O ( m n ) O(mn) O(mn)
3. Leetcode 1329. 将矩阵按对角线排序分析与解答矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。
给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100
按顺序取出每条对角线上的元素，排序后再依次放回即可。这里由于元素范围有限，因此选择直接用基数排序。当然，也可放入新数组后使用其它排序算法。
class Solution {
public:
vector> diagonalSort(vector>& mat) {
int rNum = mat.size();
int cNum = mat[0].size();
// 排列上三角
for (int j = 0; j < cNum; ++j) {
vector num;
num.resize(101, 0);
// 搜索对角线，这里首元素行列 +1 即可得到对角线元素
int r(0), c(j);
while (r < rNum && c < cNum) { // 注意边界判断，任何一个到头即结束
num[mat[r][c]]++;
r++;
c++;
}
// 按顺序向对角线填入排序后元素
r = 0;
c = j;
int numIdx(0);
while (r < rNum && c < cNum) {
while (num[numIdx] == 0) { // 跳过没有的元素
numIdx++;
}
mat[r][c] = numIdx;
num[numIdx]--; // 填入元素后更新相应元素数量
r++;
c++;
}
}
// 排列下三角
for (int i = 0; i < rNum; ++i) {
vector num;
num.resize(101, 0);
// 搜索对角线
int r(i), c(0);
while (r < rNum && c < cNum) {
num[mat[r][c]]++;
r++;
c++;
}
// 按顺序填入元素
r = i;
c = 0;
int numIdx(0);
while (r < rNum && c < cNum) {
while (num[numIdx] == 0) {
numIdx++;
}
mat[r][c] = numIdx;
num[numIdx]--;
r++;
c++;
}
}
return mat;
}
};
总结
涉及到矩阵的算法中弄清下标是最重要的，当你弄清下标之后一切都尽在掌握之中。
