一、题目
给定一个初始元素全部为 0，大小为 mn 的矩阵 M 以及记录在 M 上的一系列更新操作的数组 ops。返回操作完毕后，与mn矩阵中最大元素的个数。
输入
: m
= 3, n
= 3，operations
= [[2,2],[3,3]]
输出
: 4
解释
:
初始状态
, M
=
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
执行完操作
[2,2] 后
, M
=
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
执行完操作
[3,3] 后
, M
=
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]
M 中最大的整数是
2, 而且 M 中有
4个值为
2的元素。因此返回
4。
二、思路
算法
初始化一个 m*n 的二维数组，遍历 ops，op 的元素将决定对 M 矩阵的操作范围，操作范围就相当于循环次数的上限。将矩阵遍历到的每一个元素 +1，又因为 M[0][0] 总是被操作到的，故通过遍历 M 矩阵，返回的与 M[0][0] 相等的元素的个数。
public int maxCount(int m
, int n
, int[][] ops
) {
int[][] M
= new int[m
][n
];
for(int[] op
: ops
)
for(int i
= 0; i
< op
[0]; i
++)
for(int j
= 0; j
< op
[1]; j
++)
M
[i
][j
] += 1;
}
int cnt
= 0;
for(int i
= 0; i
< m
; i
++)
for(int j
= 0; j
< n
; j
++)
if(M
[i
][j
] == M
[0][0])
++cnt
;
return cnt
;
}
复杂度分析
时间复杂度：
O
(
m
∗
n
)
O(m * n)
O(m∗n)，空间复杂度：
O
(
m
∗
n
)
O(m * n)
O(m∗n)，
