wordpress建哪些网站吗,软件工程做项目网站,成都机械设计公司,龙溪营销型网站制作题目描述 给你一个 m x n 的矩阵 M和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] [ai, bi] 意味着当所有的 0 x ai 和 0 y bi 时#xff0c; M[x][y] 应该加 1。 在 执行完所有操作后 #xff0c;计算并返回 矩阵中最大整数的个数 。 示…题目描述 给你一个 m x n 的矩阵 M和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] [ai, bi] 意味着当所有的 0 x ai 和 0 y bi 时 M[x][y] 应该加 1。 在 执行完所有操作后 计算并返回 矩阵中最大整数的个数 。 示例
示例 1
输入: m 3, n 3ops [[2,2],[3,3]]
输出: 4
解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。示例 2
输入: m 3, n 3, ops [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
输出: 4示例 3
输入: m 3, n 3, ops []
输出: 9题解
1.初始化计数器由于所有的操作都是增加1我们只需要跟踪每个操作影响的单元格数量。 2.执行操作对于每个操作 ops[i] [ai, bi]我们增加从第0行到第 ai-1 行和第0列到第 bi-1 列的单元格数量。这意味着我们只需要考虑操作影响的行数和列数。 3.计算最大整数的个数在执行完所有操作后矩阵中最大的整数将是所有操作中最小的行影响数和列影响数。然后我们计算这个最大整数在矩阵中出现的次数这将是所有行和列的最小影响数的乘积。
代码实现
int maxCount(int m, int n, vectorvectorint ops) {int minRows m, minCols n;for (const auto op : ops) {minRows min(minRows, op[0]);minCols min(minCols, op[1]);}return minRows * minCols;
}复杂度分析
● 时间复杂度O(k)其中 k 是操作的数量。我们只需要一次遍历操作数组即可找到最小的行影响数和列影响数。 ● 空间复杂度O(1)我们只使用了常数个额外变量。 这个算法的优势在于它避免了构建和操作整个矩阵的复杂性而是通过简单的数学计算来解决问题。
