输出奇数数字序列(算法中奇数怎么表示)

导语：leetcode1252_go_奇数值单元格的数目

题目

给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个索引数组 indices，indices[i] = [ri, ci] 中的

ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。

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

示例 1：输入：n = 2, m = 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：输入：n = 2, m = 2, indices = [[1,1],[0,0]] 输出：0

解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。

提示：

1 <= n <= 50

1 <= m <= 50

1 <= indices.length <= 100

0 <= indices[i][0] < n

0 <= indices[i][1] < m

解题思路分析

1、遍历模拟；时间复杂度O(n^2)，空间复杂度O(n^2)

func oddCells(n int, m int, indices [][]int) int {arr := make([][]int, n)for i := 0; i < n; i++ {arr[i] = make([]int, m)}for i := 0; i < len(indices); i++ {r := indices[i][0]c := indices[i][1]for j := 0; j < m; j++ {arr[r][j]++}for j := 0; j < n; j++ {arr[j][c]++}}res := 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if arr[i][j]%2 == 1 {res++}}}return res}

2、统计行列；时间复杂度O(n)，空间复杂度O(n)

func oddCells(n int, m int, indices [][]int) int {rows := make([]int, n)cols := make([]int, m)for i := 0; i < len(indices); i++ {rows[indices[i][0]]++cols[indices[i][1]]++}numRows := 0for i := 0; i < n; i++ {if rows[i]%2 == 0 {numRows++}}res := 0for i := 0; i < m; i++ {if cols[i]%2 == 0 {res = res + n - numRows} else {res = res + numRows}}return res}

3、统计行列-遍历；时间复杂度O(n^2)，空间复杂度O(n)

func oddCells(n int, m int, indices [][]int) int {rows := make([]int, n)cols := make([]int, m)for i := 0; i < len(indices); i++ {rows[indices[i][0]]++cols[indices[i][1]]++}res := 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if (rows[i]+cols[j])%2 == 1 {res++}}}return res}

总结

Easy题目，遍历模拟操作直观好理解，也可以统计每行每列操作的次数进行判断

本文内容由小快整理编辑！