首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode精讲——1252. 奇数值单元格的数目(难度:简单)

LeetCode精讲——1252. 奇数值单元格的数目(难度:简单)

作者头像
爪哇缪斯
发布2023-05-10 10:05:45
2150
发布2023-05-10 10:05:45
举报
文章被收录于专栏:爪哇缪斯爪哇缪斯

一、题目

给你一个 m*n 的矩阵,最开始的时候,每个单元格中的值都是0

另有一个二维索引数组 indicesindices[i] = [ri, ci] 指向矩阵中的某个位置,其中 rici 分别表示指定的行和列(从 0 开始编号)。

indices[i] 所指向的每个位置,应同时执行下述增量操作:

ri 行上的所有单元格,加 1 。 ci 列上的所有单元格,加 1 。

给你 mnindices 。请你在执行完所有 indices 指定的增量操作后,返回矩阵中 奇数值单元格 的数目。

二、示例

2.1> 示例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.2> 示例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) 额外空间的算法来解决此问题吗?

三、解题思路

3.1> 解法1:对矩阵中元素做奇偶打标识

具体思路是,每次操作如果影响了矩阵某个元素的值时,为了作为记录,将该元素的坐标(x, y)作为key,将该元素的具体值作为value,保存到map结构中,由于最终结果是要查看奇数的个数,所以,在变更元素值的时候,一同变更奇数值总个数result这个值。

变更逻辑:因为矩阵中每个元素数值value的初始值是0,即:是偶数。所以result初始值等于0。那么当第一次执行value+1的时候,因为value值是奇数值,所以result执行加1;如果第二次执行value+1的时候,由于value值变为了偶数值,所以result同时执行减1操作。

当所有操作都执行完毕后,result值就是最终的奇数单元格个数。具体逻辑如下图所示:

这种算法的优点就是,思维逻辑比较直观,很容易第一时间想到的解法。但是它的缺点也很明显,因为题目中只是要求出奇数单元的个数,而不需要知道每个元素中具体的数值,所以这种解法无论是空间还是时间上都不是最优的。解法1的具体实现请参照4.1> 实现1:对矩阵中元素做奇偶打标识

3.2> 解法2:根据奇偶列进行计数

既然只是获取奇数单元格的个数,那么我们试图去寻找一下“奇数单元格”的规律。一个单元格是由行和列组成的。那么,indice的操作方式也是先把某一行的所有元素值都加1,然后再把某一列的所有元素值都加1。那既然是这样操作的,我们就能找到一个奇数单元格的规律——就是行和列不能同时是奇数或者偶数,也就是说行列的奇偶性应该是有差异性的,这样这个单元格(或元素)的值才会是奇数的。具体逻辑如下图所示:

那么,我们根据推导出来的公司来计算一下矩阵为m=3,n=5,indices = [[0,1],[1,1]],操作完毕之后,有多少奇数单元格。具体操作如下所示:

该解法通过我们推导出来的公式,可以不再需要解法1中的map去存储每个单元格或元素的坐标与具体值了。只是通过行列奇偶就可以计算出来技术单元格。执行速度也快了很多。解法2的具体实现请参照4.2> 实现2:根据奇偶列进行计数

四、代码实现

4.1> 实现1:对矩阵中元素做奇偶打标识

public int result = 0;

public int oddCells_slow(int m, int n, int[][] indices) {
    Map<String, Integer> map = new HashMap();
    for (int[] indice : indices) {
        compare(n, indice[0], true, map);
        compare(m, indice[1], false, map);
    }
    return result;
}

public void compare(int num, int indice, boolean reverse, Map<String, Integer> map) {
    for (int j = 0; j < num; j++) {
        String key = reverse ? (j + "," + indice) : indice + "," + j;
        Integer value = map.get(key);
        if (value == null) {
            result++;
            map.put(key, 1);
        } else {
            result = (value % 2 == 0) ? ++result : --result;
            map.put(key, ++value);
        }
    }
}

4.2> 实现2:根据奇偶列进行计数

public static int oddCells(int m, int n, int[][] indices) {
    boolean[] row = new boolean[m], column = new boolean[n];
    int rowNum = 0, columnNum = 0;
    for (int[] indice : indices) {
        rowNum += (row[indice[0]] = !row[indice[0]]) ? 1 : -1; // 计算【奇数行】的个数
        columnNum += (column[indice[1]] = !column[indice[1]]) ? 1 : -1; // 计算【奇数列】的个数
    }

    // 【奇】行数 * 【偶】列数 + 【奇】列数 * 【偶】行数
    return rowNum * (n - columnNum) + columnNum * (m - rowNum); 
}

今天的文章内容就这些了,最后一句话:

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-07-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爪哇缪斯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
  • 二、示例
    • 2.1> 示例1:
      • 2.2> 示例2:
        • 提示:
          • 进阶:
          • 三、解题思路
            • 3.1> 解法1:对矩阵中元素做奇偶打标识
              • 3.2> 解法2:根据奇偶列进行计数
              • 四、代码实现
                • 4.1> 实现1:对矩阵中元素做奇偶打标识
                  • 4.2> 实现2:根据奇偶列进行计数
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档