奇数值单元格的数目
难度:
标签:
题目描述
给你一个 m x n
的矩阵,最开始的时候,每个单元格中的值都是 0
。
另有一个二维索引数组 indices
,indices[i] = [ri, ci]
指向矩阵中的某个位置,其中 ri
和 ci
分别表示指定的行和列(从 0
开始编号)。
对 indices[i]
所指向的每个位置,应同时执行下述增量操作:
ri
行上的所有单元格,加1
。ci
列上的所有单元格,加1
。
给你 m
、n
和 indices
。请你在执行完所有 indices
指定的增量操作后,返回矩阵中 奇数值单元格 的数目。
示例 1:
输入:m = 2, n = 3, indices = [[0,1],[1,1]] 输出:6 解释:最开始的矩阵是 [[0,0,0],[0,0,0]]。 第一次增量操作后得到 [[1,2,1],[0,1,0]]。 最后的矩阵是 [[1,3,1],[1,3,1]],里面有 6 个奇数。
示例 2:
输入:m = 2, n = 2, indices = [[1,1],[0,0]] 输出:0 解释:最后的矩阵是 [[2,2],[2,2]],里面没有奇数。
提示:
1 <= m, n <= 50
1 <= indices.length <= 100
0 <= ri < m
0 <= ci < n
进阶:你可以设计一个时间复杂度为 O(n + m + indices.length)
且仅用 O(n + m)
额外空间的算法来解决此问题吗?
代码结果
运行时间: 26 ms, 内存: 16.1 MB
/*
* 给你一个 m x n 的矩阵,最开始的时候,每个单元格中的值都是 0。
* 另有一个二维索引数组 indices,indices[i] = [ri, ci] 指向矩阵中的某个位置,
* 其中 ri 和 ci 分别表示指定的行和列(从 0 开始编号)。
* 对 indices[i] 所指向的每个位置,应同时执行下述增量操作:
* 1. ri 行上的所有单元格,加 1 。
* 2. ci 列上的所有单元格,加 1 。
* 给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后,返回矩阵中 奇数值单元格 的数目。
*/
import java.util.stream.IntStream;
public class Solution {
public int oddCells(int m, int n, int[][] indices) {
int[] rows = new int[m];
int[] cols = new int[n];
for (int[] index : indices) {
rows[index[0]]++;
cols[index[1]]++;
}
long oddRows = IntStream.of(rows).filter(x -> x % 2 != 0).count();
long oddCols = IntStream.of(cols).filter(x -> x % 2 != 0).count();
return (int) (oddRows * (n - oddCols) + oddCols * (m - oddRows));
}
}
解释
方法:
首先,初始化一个 m x n 的矩阵 M,所有元素初始值为 0。针对给定的 indices 数组,每个 [ri, ci] 表示一次操作,即将第 ri 行的所有元素值加 1,和将第 ci 列的所有元素值加 1。操作完成后,遍历整个矩阵 M,统计奇数值单元格的数量并返回这个计数。
时间复杂度:
O(l * (m + n) + m * n)
空间复杂度:
O(m * n)
代码细节讲解
🦆
在算法中,你是如何处理行和列的增加操作以避免重复增加同一个单元格的值?
▷🦆
为什么在统计奇数值单元格时选择遍历整个矩阵,而不是在增加操作时直接统计奇数值的变化?
▷🦆
在实现中,每次增加操作都涉及整行和整列的更新,这是否意味着对同一行或列多次操作时会有冗余计算?如何优化?
▷🦆
如果indices数组为空,或者m和n中的任何一个为0,题解中的算法是否处理了这些特殊情况?
▷